Vérifier est plus facile que de trouver?
trouver une solution à un problème devrait être plus difficile que de vérifier qu’une solution est correcte. Cela semble évident si vous avez déjà résolu un puzzle de sudoku, résolu un Rubik’s cube ou joué à une partie d’Échecs. Mais cette affirmation, aussi intuitive soit-elle, nous conduit directement à l’une des questions mathématiques les plus profondes posées par notre civilisation.
Les problèmes de temps polynomial non déterministe (ou NP) sont ceux où vous pouvez facilement vérifier qu’une réponse est correcte., En revanche, les problèmes de temps polynomial (ou P) sont ceux
où trouver la réponse est facile. Si vous pouvez trouver la réponse, alors vous avez vérifié qu’elle est correcte, donc chaque problème dans P est également dans NP. Nous disons que P est une sous-classe de NP. Cependant, nous ne savons pas s’il y a un problème particulier dans NP qui n’est pas dans P, et c’est ce que nous appelons le problème P vs NP.
le problème P vs NP est l’un des problèmes non résolus les plus centraux en mathématiques et en informatique théorique. Il existe même un prix Clay Millennium offrant un million de dollars pour sa solution., Cependant, il existe probablement des moyens beaucoup plus faciles de devenir millionnaire que de résoudre P vs NP!
Il y a eu un buzz récemment quand quelqu’un a prétendu le résoudre sur arXiv, bien qu’une lacune dans la preuve ait été rapidement trouvée. Compte tenu de l’intérêt récent pour le problème et sa place centrale dans les mathématiques, j’en discute dans le blog de cette semaine.
Sudoku
Si vous recevez un puzzle de Sudoku rempli dans un journal, vous pourriez le jeter dans la poubelle. Mais si vous le vouliez, vous pouvez parcourir les lignes, les colonnes et les cellules 3 x 3 pour dire que c’est une solution valide: chacun des 1, 2, … , 9 doit se produire exactement une fois., Qui est analogue à NP, car il est relativement facile de vérifier si une solution est correcte.
cependant, si je vous donne un puzzle de Sudoku partiellement rempli, il peut être difficile de trouver la solution. C’est la joie et le défi de ce genre de puzzle. Donc, être dans NP ne semble pas immédiatement impliquer que le problème a une solution facile à trouver. Cette intuition est au cœur du problème P vs NP.
formulation précise
Pour comprendre P et NP plus précisément, il faut mieux comprendre les algorithmes et mesurer leur vitesse. Des problèmes sont posés avec certaines entrées et sorties fixes oui ou non. L’entrée est d’une longueur donnée, disons n, où n est un entier positif. Cela représente le nombre de bits qu’il faut pour exprimer l’entrée. Un algorithme est une méthode ou une procédure pour résoudre un problème. Les algorithmes fournissent des instructions à chaque étape d’un calcul et doivent se terminer., Les étapes peuvent être des secondes, des millisecondes ou un autre intervalle de temps fixe qui dépend de votre problème.
la complexité d’un problème est le temps d’exécution minimum dans le pire des cas sur tous les algorithmes possibles résolvant le problème en fonction de la longueur de l’entrée. En d’autres termes, il mesure le temps nécessaire pour résoudre le problème avec l’algorithme le plus rapide mais avec l’entrée du pire des cas.
un problème est résoluble en temps polynomial si on lui donne une entrée de longueur n, sa complexité est limitée au-dessus par la fonction polynomiale nm pour un entier non négatif M., L’ensemble de tous les problèmes résolubles en temps polynomial est noté P.
être dans P ne signifie pas nécessairement que le problème est réalisable. Par exemple, s’il faut n1000 étapes pour exécuter l’algorithme, il sera désespérément lent même pour les petits n. les problèmes polynomiaux Non déterministes (ou NP) sont ceux où vous pouvez vérifier si la réponse OUI est correcte en temps polynomial.
NP-dureté
Un problème est NP–difficile si un polynôme en temps de l’algorithme pour qu’elle impliquerait un polynôme en temps de l’algorithme pour chaque problème dans NP. Par conséquent, si un problème NP-dur était dans P, alors P = NP., Les problèmes NP-hard sont au moins aussi difficiles que n’importe quel problème dans NP. Un problème NP-complet est un problème qui est NP-dur et dans NP.
un problème NP-complet classique consiste à trouver un cycle de Hamilton. Pour cela, supposons que nous ayons un réseau de villes reliées par des routes. Le problème est de visiter chaque ville en utilisant des routes (pas d’avions autorisés!) et de revenir au point de départ. Cela semble facile pour un petit nombre de villes, mais si on vous en a donné des centaines, cela devient difficile., Des milliers d’autres problèmes NP-complets de ce type sont connus en théorie des graphes, en théorie des nombres, en Géométrie et dans d’autres domaines des mathématiques et de l’informatique.
Quelle est la réponse, vraiment?
Si je devais parier, alors je supposerais que P n’est pas égal à NP, et je pense que la plupart des experts seraient d’accord. Nous devrions être terriblement stupides pour ne pas voir comment tous les milliers de problèmes NP-complets n’ont pas d’algorithme de temps polynomial. Mais en tant qu’espèce, dumb est notre position par défaut, donc personne ne peut dire quelle est la réponse avec 100% de certitude.,
ce qui est intéressant à propos du problème P vs NP, c’est qu’il indique à quel point notre compréhension est limitée pour prouver que certains problèmes n’ont pas de solutions rapides. Cela fait partie d’un thème plus large dans le domaine de la théorie de la complexité computationnelle, qui étudie des dizaines d’autres classes de complexité. Consultez le zoo de la complexité pour une liste de ces classes. Pour la plupart, il est ouvert pour montrer diverses classes de complexité (souvent exotiques) sont des sous-classes appropriées les unes des autres. Par exemple, on ne sait pas si NL est une sous-classe appropriée de P, et nous ne savons pas si FPT est une sous-classe appropriée de W.,
quelle que soit sa véracité, le problème P vs NP est susceptible de rester ouvert pendant un certain temps. À moins qu’il ne soit prouvé que P = NP, le Sudoku reste sûr.
Anthony Bonato