le problème P contre NP vieilli
alors, qu’est-ce que le problème P contre NP?
Pour mémoire, le statu quo est que P NP NP.
p (temps polynomial) fait référence à la classe de problèmes qui peuvent être résolus par un algorithme en temps polynomial. Les problèmes de la classe P peuvent aller de la simple multiplication à la recherche du plus grand nombre dans une liste. Ils constituent l’ensemble de problèmes relativement « plus faciles ».
NP (temps polynomial non déterministe) fait référence à la classe de problèmes qui peuvent être résolus en temps polynomial par un ordinateur non déterministe., C’est essentiellement une autre façon de dire « si j’ai une puissance de calcul illimitée (c’est-à-dire autant d’ordinateurs que nécessaire), je suis capable de résoudre n’importe quel problème au plus tard en temps polynomial”. Plus intuitivement cependant, il fait référence à la classe de problèmes qui n’a actuellement aucun moyen de trouver une réponse rapide (en temps polynomial), mais peut être rapidement vérifiée (en temps polynomial) si l’on fournit la solution au problème. Le terme vérifié ici signifie que l’on peut vérifier que la solution fournie est bien correcte.
clairement, sur la base de la définition ci-dessus, P NP NP., Prenons un oeil à un exemple pour illustrer ce problème abstrait.
L’un des exemples les plus courants mais efficaces est le Sudoku. Étant donné une grille de Sudoku non résolue (9 x 9 par exemple), il faudrait un algorithme assez de temps pour en résoudre un. Cependant, si la grille 9 x 9 augmente à une grille 100 x 100 ou 10 000 x 10 000, le temps qu’il faudrait pour la résoudre augmenterait exponentiellement car le problème lui-même devient beaucoup plus difficile., Cependant, étant donné une grille de Sudoku résolue (de 9 x 9), Il est assez simple de vérifier que la solution particulière est bien correcte même si la taille varie de 10 000 à 10 000. Il serait plus lent, mais le temps de vérifier une solution augmente à un rythme plus lent (polynomialement).
Il existe de nombreux autres problèmes NP, y compris le problème du sac à dos et le problème des vendeurs itinérants, et ils sont similaires en ce sens qu’ils sont difficiles à résoudre mais rapides à vérifier., Le problème fondamental que nous essayons de résoudre ici est le suivant:
le fait de pouvoir reconnaître rapidement les bonnes réponses NP signifie-t-il qu’il existe également un moyen rapide de les trouver?
Si oui (c’est-à-dire P=NP), cela pourrait grandement changer la façon dont nous regardons ces problèmes NP car cela signifie qu’il existe un moyen rapide de résoudre tous ces problèmes, juste que nous n’avons pas encore pu comprendre comment.
si ce n’est pas assez compliqué, pimentons-le.,
parmi ces problèmes NP, il existe un roi de tous les problèmes que les chercheurs appellent les problèmes NP-complets. Formellement, ils sont un ensemble de problèmes à chacun desquels tout autre problème NP peut être réduit (abordé ci-dessous) en temps polynomial et dont la solution peut encore être vérifiée en temps polynomial. Cela signifie que tout problème NP peut être transformé en un problème NP-complet.
officieusement, ils sont les « plus difficiles” des problèmes NP., Donc si quelqu’un NP-Complets problème peut être résolu en temps polynomial, alors chaque NP-Complets problème peut être résolu en temps polynomial, et tous les problèmes de NP peut être résolu en temps polynomial (c’est à dire P=NP). L’exemple le plus célèbre serait le problème des vendeurs itinérants.
Il existe aussi un ensemble de problèmes NP-Difficiles problèmes., Ces problèmes sont au moins aussi difficiles que les problèmes NP, mais sans la condition qui exige qu’il soit résolu en temps polynomial. Cela suggère que les problèmes NP-durs ne font pas nécessairement partie de la classe NP. Un exemple serait de résoudre un échiquier — étant donné un État d’un échiquier, il est presque impossible de dire si un coup donné à l’état donné, est en fait le coup optimal. Formellement, il n’existe pas d’algorithme de temps polynomial pour vérifier une solution à un problème NP-dur.,
Si nous mettons les deux ensemble, un problème NP-complet implique QU’il est NP-dur, mais un problème NP-dur n’implique pas QU’il est NP-complet.
définition de NP-complétude
un problème l, est NP-complet si:
- l est NP-dur
- L appartient à NP
Le diagramme ci-dessous (focus sur le côté gauche) devrait rendre les choses plus claires.,
Wait, what does it mean by reducing A to B?
Reduction forms the crux of NP-Completeness.,
de manière informelle, un problème L1 peut être réduit à un autre problème L2 si:
- toute instance de L1 peut être modélisée comme une instance de L2
- la solution à cette dernière fournit une solution à la première et vice versa
pour comprendre cela intuitivement, on peut le penser comme tel:
est réductible à L2, L1 doit être au plus aussi dur que L2. Inversement, L2 doit être au moins aussi dur que L1.
mathématiquement, cela est noté: L1 ≤p L2 (lire comme « L1 est polynomialement réductible à L2”).,
