Bonjour,
en quoi le fait qu'un problème de décision puisse être résolu en temps polynomial par une machine de Turing non déterministe est-il équivalent au fait que toute solution candidate à ce problème puisse être décidée en temps polynomial par une machine de Turing déterministe svp ?
Merci.
S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une
SAlut,
C'est simple, ce n'est pas le cas. Sur une turing déterministe c'est non polynomial en générale (sauf avec "certificat", on emploie aussi le terme d'oracle ou de vérification en temps polynomial de la solution, les démos sont très compliquées mais qu'une machine ayant un indice sur la solution trouve vite la solution, c'est pas si étonnantEnvoyé par ilelogique
).
Exemple : le voyageur de commerce, il est NP (et même NP complet) et demande un temps exponentiel sur une machine "normale", déterministe
Je ne sais pas ce que tu as lu où il y avait ça mais amha tu as mal lu (faut dire que les formulations sont assez abstraites, comme dans wikipedia par exemple)
Ou peut-être est-ce toi qui a rédigé de manière peu claire (tu parles de "résolu et décidé" = résolu et vérifié ???), si c'est les démos que tu cherches doit bien y avoir quelqu'un qui te donnera ça ic, mais accroche toi !!!!!
Dernière modification par Deedee81 ; 28/01/2022 à 09h16.
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
Navré, je pensais m'être bien exprimé, je tente de redire...
1) Je croyais qu'un problème de décision était NP lorsqu'il était calculable en temps polynomial sur une MT non déterministe.
2) Je pensais par ailleurs que pour tout problème de décision NP il y avait une MT déterministe qui pouvait décider (dire oui ou non) en temps polynomial pour une instance donnée du problème, un candidat, une certaine proposition de solution (dire si un chemin donné est inférieur à k par exemple pour le pb du VC).
Du coup je me demande pourquoi 1) <=> 2) ???
S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une
Ah désolé, tu avais bien compris.
Et pour la réponse, attendons le passage d'un spécialiste ou un lien vers la démo (mais pas simple et j'ignore si on peut l'expliquer en quelques mots)
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
l'idée que je m'en fais, mettons avec vc (n,k) (n villes et k la longueur maxi qu'on cherche) c'est qu'avec une MT non déterministe, on peut imaginer autant de rubans qu'il y a de chemins et que chaque ruban teste en temps polynomial son chemin et qu'on est donc pas loin pour chaque ruban d'une MT déterministe. Au fond une MT non déterministe ne revient-elle pas à un nombre arbitrairement grand de MT déterministes ?
S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une
En fait je ne cherche pas de preuve formelle de cette équivalence mais déjà d'une idée intuitive de la raison disons...
S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une
Oui, c'est ça, c'est "massivement parallèle".
Ou plutôt arborescent et donc exponentiel (en nombre de transitions en parallèle). Et donc pour un problème de complexité exponentielle il est compréhensible que la machine non déterministe puisse trouver en un temps polynomial.
Et de même sur l'exemple avec le voyageur de commerce la vérification polynomiale est facile avec une machine déterministe.
Mais ça ne constitue évidemment pas une preuve rigoureuse ni même une justification générale pour la question posée, juste un raisonnement intuitif et un exemple parlant
EDIT mais selon ton message précédent, c'est peut-être suffisant ?
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
Merci FS, parfois ici, le seul fait de poser sa question permet d'y répondre...
"Massivement", j'aime bien le terme, en maths ça ferait tout le monde sauf une quantité négligeable,
merci,
Je ne ferme pas le sujet car il est encore ouvert,
déjà, pourquoi NP ? ça prête à confusion, on croît que ça veut dire "Non Polynomial", alors que c'est : calculable en machine de Turing Non Déterministe, P=ND serait déjà mieux...
C'est le test de primalité qui tranche, oui c'est sûr, nous n'avions pas trouvé d'algorithme polynomial et maintenant il y en a un, donc être dans NP sans être dans P ne veut pas dire qu'on n'y rentrera pas un jour...
Merci
S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une
