Bonjour à toutes et à tous,
Je croyais avoir compris les tenants du problème P=NP, mais je me suis rendu compte que ce que je croyais était paradoxal. Pouvez-vous m'aider à me corriger ?
Il me semblais que l'on pouvait définir le problème P=NP de la manière suivante :
- La classe P est celle des problèmes de décision pour lesquels il existe un algorithme répondant au problème dont le temps d'exécution est polynomial en la taille du problème.
- La classe NP (pour “nondeterministic polynomial”) est celle des problèmes de décision pour lesquels on peut valider une réponse fournie par un oracle en temps polynomial.
- P=NP est le problème "Tout les problèmes NP sont-ils des problèmes P ?"
Ainsi, il a été démontré que le fameux problème du sudoku fait parti de la classe NP (et même NP-complet mais je ne m’étendrais pas dessus), et il peut être définit ainsi :
"Etant donné une matrice n²*n² partiellement remplie d'entiers, est-il possible de compléter toute la grille en suivant les règles du sudoku ?"
Et effectivement, je me rend bien compte qu'on peut réaliser un algorithme vérifiant si une grille déjà complété est valide ou non en temps polynomial.
Or, un problème décision est une question mathématique dont la réponse est soit « Vrai », soit « Faux ». Ce que je ne comprend pas, c'est la nature de la réponse fournie par l'oracle. Pour un problème de décision les seules réponses valables sont donc Vrai ou Faux, donc l'oracle devrait fournir comme réponse simplement "Vrai" ou simplement "Faux". Or pour le sudoku j'ai l'impression que l'on s'attend à ce que l'oracle nous donne pas seulement une réponse mais aussi une justification en l’occurrence la grille complété entièrement si Vrai ou la grille complété de tel manière qu'un blocage dans la résolution est trivial si Faux.
Une autre manière de mettre en évidence que je n'ai pas bien compris le problème P=NP, en partant de la définition de la classe NP j'ai l'impression que l'on peut dire ce qui suit.
Soit F(x) un problème ayant pour entrée une donnée x, soit n la taille de x, alors F appartiens à NP si et seulement si :Ce qui entraînerait que les propositions "F(x) a pour solution Vrai" et "F(x) a pour solution Faux" sont évaluable toutes les deux en un temps polynomial et couvrira toutes les réponse possibles de F(x), ce qui impliquerais trivialement P=NP.
- La proposition "F(x) a pour solution y" est déterminable en temps polynomial en x quelque soit x et y.
- F(x) est un problème de décision quelque soit x, donc sa solution sera soit Vrai soit Faux.
Voilà, je serais ravi que quelqu'un me remette de l'odre dans mes idées car j'arrive pas à comprendre ce que je n'ai pas saisie même en allant consulter des articles de vulgarisation sur le problèmeComme dit plus haut je pense que mon problème est que dans la définition d'un problème NP j'ai mal saisi la nature d'une réponse fournie par un oracle.
Merci d'avance aux courageux pour votre aides !
Azerus.
-----