Problèmes de décisions, et problème P=NP

[invitee11e5e5a]

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 :

• 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.

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.


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ème Comme 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.
-----

[invite046e427d]

Salut,

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.

Je ne répondrai pas à tout ton post sous peine de dire de grosses bêtises.
Différemment à l'intuition donnée sur wiki, je pense qu'il faut voir cet objet mathématique qui pour l'instant reste théorique comme une mécanique abstraite d'où la grande difficulté à en rendre compte concrètement. Ce n'est pas l'oracle qui te dira vrai ou faux mais une logique (si je peux me permettre) de traduction de sa réaction.
Cdt

[invitee11e5e5a]

Merci Noress pour ta réponse.

Oui je comprend bien que l'oracle fonctionne comme une boite noire et je comprend tout à fait que tu parles de mécanique abstraite. Néanmoins, il y a toujours quelque chose qui me turlupine dans la définition de la classe NP que j'ai en tête...

Tiens je viens de voir qu'il y a justement un article qui parle des oracles sur Wiki : https://fr.wikipedia.org/wiki/Oracle...ine_de_Turing)

Si je trouve la réponse à mes questions avant que quelqu'un ne réponde je la posterais ici.

Sinon, je suis un passionné de math (notamment mathématiques fondamentales, théorie des nombres, théorie de l'information, ...) et je travail en tant qu'ingénieur software. J'ai malheureusement quasiment pas eu de cours d'informatique théorique à l'école alors que j'aurais adoré ! C'est pourquoi j'aimerais avoir une bonne représentation de ce problème, s'il faut j'irais me trouver un bouquin.