Répondre à la discussion
Affichage des résultats 1 à 16 sur 16

Problème NP-complet indécidable



  1. #1
    benoir126

    Problème NP-complet indécidable


    ------

    Bonjour,

    est-ce que NP-complet == indécidable ?

    Donnez un exemple de problème NP-complet indécidable pour l'expliquer.

    Merci bcp de votre aide

    -----

  2. Publicité
  3. #2
    Gre

    Thumbs down Re : Problème NP-complet indécidable

    Citation Envoyé par benoir126 Voir le message
    Bonjour,

    est-ce que NP-complet == indécidable ?

    Donnez un exemple de problème NP-complet indécidable pour l'expliquer.

    Merci bcp de votre aide
    Jolie la question de cours.
    T'en a une autre ?
    War does not decide who's right, but who's left. (Bertrand Russell)

  4. #3
    championnet

    Re : Problème NP-complet indécidable

    un problème NP-complet est forcément décidable.

    Les problèmes NP-complets sont, si on veut, les plus durs de la classe NP. Et par définition, un problème est dans la classe NP si il existe une machine de Turing non-deterministe en temps polynomial qui décide ses instances...

    Faut revoir ton cours, mon vieux

  5. #4
    GuYem

    Re : Problème NP-complet indécidable

    Ca pète sec ici !
    Bravo jolie Ln, tu as trouvé : l'armée de l'air c'est là où on peut te tenir par la main.

  6. A voir en vidéo sur Futura
  7. #5
    benoir126

    Re : Problème NP-complet indécidable

    Citation Envoyé par championnet Voir le message
    un problème NP-complet est forcément décidable.

    Les problèmes NP-complets sont, si on veut, les plus durs de la classe NP. Et par définition, un problème est dans la classe NP si il existe une machine de Turing non-deterministe en temps polynomial qui décide ses instances...

    Faut revoir ton cours, mon vieux
    Tout d`abord, merci de votre réponse!
    un problème est dans la classe NP si il existe une machine de Turing non-deterministe en temps polynomial qui décide ses instances...Oui, je suis d'accord,
    Mais, on ne dit pas que NP == NP-complet.
    le problème TSP est un problème NP-hard,un cycle est decidable si c'est un cycle hamiltonien , mais si c'est le plus petit cycle hamiltonien est indécidable.
    alors... TSP est indécidable et NP-complet ?

  8. #6
    Taar

    Re : Problème NP-complet indécidable

    Salut !

    Citation Envoyé par benoir126 Voir le message
    mais si c'est le plus petit cycle hamiltonien est indécidable.
    Ben non, savoir si un cycle hamiltonien donné de longueur n est le plus petit cycle hamiltonien (pour des poids donnés) n'est pas indécidable, même par une machine déterministe. Il suffit de regarder, partant d'un sommet donné, tous les parcours de longueur n. C'est lourd, mais décidable.

    Tu peux préciser ce que tu entends (dans le cas des graphes finis bien sûr) ?

    Taar.

  9. Publicité
  10. #7
    benoir126

    Re : Problème NP-complet indécidable

    Citation Envoyé par Taar Voir le message
    Salut !



    Ben non, savoir si un cycle hamiltonien donné de longueur n est le plus petit cycle hamiltonien (pour des poids donnés) n'est pas indécidable, même par une machine déterministe. Il suffit de regarder, partant d'un sommet donné, tous les parcours de longueur n. C'est lourd, mais décidable.

    Tu peux préciser ce que tu entends (dans le cas des graphes finis bien sûr) ?

    Taar.
    Merci Taar.
    Bon, c'est plus clair. Alors on peux dire que tous les problèmes NP-complet sont décidables ??
    Ben, un problème indécidable alors n'est pas un problème NP-complet ??
    Dernière modification par benoir126 ; 07/03/2007 à 00h52.

  11. #8
    Taar

    Re : Problème NP-complet indécidable

    Exactement. NP-complet implique décidable. Je confirme ce que disait championnet.

    Taar.

  12. #9
    championnet

    Re : Problème NP-complet indécidable

    Les Problèmes NP-complets forment une partie de l'ensemble des problèmes NP (ce sont, en gros, les "plus durs").

    Au passage, pour reprendre ton raisonnement sur les circuits hamiltoniens, il faut être prudent : être NP-dur ne signifie pas forcément être NP-complet. En effet, un problème est NP-complet si :
    1. Il est NP-dur
    2. Il est dans NP

    Suivant les cas, c'est l'une ou l'autre des propriétés qui est dure à prouver. Un problème dans une classe supérieure à NP (genre, PSPACE, EXPTIME, etc.) sera évidemment NP-dur. Mais il ne sera pas dans NP.

    En gros, dire qu'un problème est dans NP donne une borne supérieure sur sa complexité. Dire qu'il est NP-dur donne une borne inférieure (il est "au moins aussi dur que n'importe quel autre dans NP").

    Des problèmes indécidables peuvent être NP-dur (voire même : ils le sont tous ? à vérifier. A priori le problème de l'arret des machines de Turing, indécidable, est NP-dur). Par contre ils ne peuvent pas être dans NP, parce que sinon ils seraient décidables.

    Encore une fois, je ne peux que tu suggérer de prendre un manuel/cours de complexité, et de bien lire les définitions, car à mon avis tout ceci est encore un peu flou pour toi....

    bon courage en tout cas !

  13. #10
    benoir126

    Re : Problème NP-complet indécidable

    très bonne réponse.
    Merci à Taar,championnet !!!

  14. #11
    benoir126

    Re : Problème NP-complet indécidable

    Merci à Taar,championnet

    Je me pose une question peut-être ridicule,
    pour moi :

    Un probleme appartient a P s'il est decidable en temps polynomial

    Un probleme appartient a NP si on peut verifier une reponse "candidate" en un temps polynomial.

    alors, on peut dire que Un probleme NP est decidable ? si oui, alors tous les problemes indécidables sont pas les problemes NP-complets .

    Merci d'avance!

  15. #12
    championnet

    Re : Problème NP-complet indécidable

    Un problème NP est décidable, c'est ce que j'ai dit 2 fois dans 2 messages différents au dessus

    Voici comment :
    1) détermine (une borne supérieure sur) la taille du candidat, qui est une fonction polynomiale de la taille de l'entrée (par définition)
    2) énumère tous les candidats possibles de cette taille-là
    3) utilise le fait qu'on peut décider en temps polynomial si un candidat est bon sur tous les candidats. Si l'un d'entre eux est un bon candidat, tu as ta réponse. S'ils sont tous de mauvais candidats, tu as ta réponse aussi.

    ça termine en un temps exponentiel en la taille des candidats.

    Pour la deuxième partie de ta reflection ("alors, on peut dire que Un probleme NP est decidable ? si oui, alors tous les problemes indécidables sont pas les problemes NP-complets.")

    Déjà, d'un point de vue grammatical, cette question st louche

    AUCUN problème indécidable n'est NP-complet tout simplement parce que être NP-complet implique être dans NP implique être décidable (cf. raisonnement ci-dessus).

    J'espère que je suis clair ?

  16. Publicité
  17. #13
    benoir126

    Re : Problème NP-complet indécidable

    Citation Envoyé par championnet Voir le message
    Un problème NP est décidable, c'est ce que j'ai dit 2 fois dans 2 messages différents au dessus

    Voici comment :
    1) détermine (une borne supérieure sur) la taille du candidat, qui est une fonction polynomiale de la taille de l'entrée (par définition)
    2) énumère tous les candidats possibles de cette taille-là
    3) utilise le fait qu'on peut décider en temps polynomial si un candidat est bon sur tous les candidats. Si l'un d'entre eux est un bon candidat, tu as ta réponse. S'ils sont tous de mauvais candidats, tu as ta réponse aussi.

    ça termine en un temps exponentiel en la taille des candidats.

    Pour la deuxième partie de ta reflection ("alors, on peut dire que Un probleme NP est decidable ? si oui, alors tous les problemes indécidables sont pas les problemes NP-complets.")

    Déjà, d'un point de vue grammatical, cette question st louche

    AUCUN problème indécidable n'est NP-complet tout simplement parce que être NP-complet implique être dans NP implique être décidable (cf. raisonnement ci-dessus).

    J'espère que je suis clair ?
    salut,

    c'est très clair !!!!!!!!


  18. #14
    Tony2014

    Re : Problème NP-complet indécidable

    Bonjour,

    J'interviens en retard dans la discussion. Les arguments de chamionnet et Taar sont très clairs. Cependant je me pose une question par rapport à la conjecture P=NP, elle même indécidable. Apparemment, on peut démontrer qu'un problème P-complet est indécidable, donc un problème indécidable peut être exprimé sous forme P complète:
    http://www2.lifl.fr/~delahaye/HECI/Calcul.pdf
    Dès lors le fait que la réduction NP=P soit elle-même indécidable ne devrait-il pas à considérer qu contraire que l'on ne peut pas exclure à priori l'existence de problèmes à la fois NP-complets et indécidables?
    Dernière modification par Tony2014 ; 23/05/2014 à 23h52.

  19. #15
    gg0
    Animateur Mathématiques

    Re : Problème NP-complet indécidable

    par rapport à la conjecture P=NP, elle même indécidable
    Tu es vraiment sûr de ça ?

    Cordialement.

  20. #16
    Bluedeep

    Re : Problème NP-complet indécidable

    Citation Envoyé par Tony2014 Voir le message
    J'interviens en retard dans la discussion
    Meuh non : juste 7 ans; une paille

Discussions similaires

  1. Hypothèse de Riemann indécidable ?
    Par azt dans le forum Mathématiques du supérieur
    Réponses: 139
    Dernier message: 01/09/2012, 17h29
  2. NP-Complet vs NP-Difficile !!!!
    Par Polytechnicienne dans le forum Mathématiques du supérieur
    Réponses: 13
    Dernier message: 20/12/2010, 08h28
  3. Espace de Baire non complet?
    Par indian58 dans le forum Mathématiques du supérieur
    Réponses: 22
    Dernier message: 21/01/2008, 17h03
  4. Problème mesure sur pont complet
    Par telecofr dans le forum Électronique
    Réponses: 16
    Dernier message: 25/12/2006, 16h22