vignette|400px|Représentation visuelle des deux configurations possibles.
Le problème est une conjecture en mathématiques, et plus précisément en informatique théorique, considérée par de nombreux chercheurs comme une des plus importantes conjectures du domaine, et même des mathématiques en général. L'Institut de mathématiques Clay a inclus ce problème dans sa liste des sept problèmes du prix du millénaire , sur le site de l'Institut Clay., et offre à ce titre un million de dollars à quiconque sera en mesure de démontrer ou ou de démontrer que ce n'est pas démontrable. Ce problème est également le troisième problème de Smale.
Très schématiquement, il s'agit de déterminer si le fait de pouvoir vérifier rapidement une solution à un problème implique de pouvoir la trouver rapidement ; ou encore, si ce que nous pouvons trouver rapidement lorsque nous avons de la chance peut être trouvé aussi vite par un calcul intelligent.
Plus précisément, il s'agit de savoir si la classe de complexité des problèmes de décision admettant un algorithme de résolution s'exécutant en temps polynomial sur une machine de Turing est équivalente à la classe de complexité des problèmes de décision dont la vérification du résultat, une fois celui-ci connu, demande un temps polynomial. Un algorithme qui demande un temps d'exécution polynomial est généralement considéré comme « rapide » (par rapport à un temps d'exécution exponentiel par exemple).
À condition que le degré du polynôme issu du caractère polynomial de l'algorithme soit raisonnable, les conséquences de pourraient être considérables dans de nombreux domaines : cryptologie, informatique, mathématiques, ingénierie, économie. S'il était prouvé que , alors la résolution de tous les autres problèmes posés par l’Institut Clay pourrait devenir évidenteParagraphe « What if "P=NP"? ».p. 6. S'il était au contraire avéré que , cela signifierait qu'une large classe de problèmes seraient presque sûrement définitivement hors d'atteinte du calcul dans un temps raisonnable (ou nécessiteraient le développement d'architectures différentes de celles des machines de Turing).
Présentation informelle Voici comment le problème est présenté par l'Institut ClayP vs NP sur le site du Clay Mathematics Institute..
Supposons que vous soyez chargé de loger un groupe de quatre cents étudiants. Le nombre de places est limité, seuls cent étudiants se verront attribuer une place dans la résidence universitaire. Pour compliquer les choses le doyen vous a fourni une liste de paires d'étudiants incompatibles, et demande que deux étudiants d'une même paire ne puissent jamais apparaître dans votre choix final. C'est un exemple de ce qu'un informaticien appelle un problème . En effet, il vous est facile de vérifier qu'une liste de cent étudiants fournie par un collègue est correcte, c'est-à-dire que les étudiants d'une même paire de la liste du doyen n'apparaissent jamais tous deux dans la liste de votre collègue. Toutefois, produire une telle liste à partir de zéro paraît tellement difficile qu'elle en est même impraticable, car le nombre de façons de regrouper cent étudiants parmi quatre cents dépasse le nombre d'atomes de l'univers ! Pour cette raison, aucune civilisation du futur ne peut même espérer construire un super-ordinateur capable de résoudre ce problème par force brute, c'est-à-dire en testant toutes les combinaisons de cent étudiants. Peut-être que cette apparente difficulté ne fait que refléter le manque d'ingéniosité de nos programmeurs. Il s'avère que l'une des questions les plus importantes de la science informatique est de savoir s'il existe des problèmes dont la solution peut être vérifiée rapidement, mais qui requièrent un temps incroyablement long pour être résolus par un quelconque procédé.[…] Stephen Cook et Leonid Levin ont formulé indépendamment le problème (facile à trouver) vis-à-vis de (facile à vérifier) en 1971.
Complexité des algorithmes, classes et
Importance et implications de Un des aspects essentiels de ce problème provient du fait qu'il existe une classe de problèmes très importants dits « -complets » qui est la sous-classe de dont les problèmes sont au moins aussi durs que tous les problèmes de , autrement dit les problèmes les plus durs de . Ils sont importants à double titre : d'une part, ils possèdent souvent une importance intrinsèque (de nombreux problèmes fondamentaux, à incidences pratiques, dans plusieurs domaines étant -complets) et, d'autre part, par définition de la -complétude, si on trouve une solution en temps polynomial à l'un de ces problèmes, alors cette solution peut être utilisée pour résoudre, en temps polynomial, tous les problèmes -complets, et plus généralement tous les problèmes . Le théorème de Cook montre que le problème SAT est -completLeonid Levin avait pris comme point de départ un problème de pavage., ce résultat a ensuite été largement réutilisé pour établir une liste de problèmes -complets.
Les problèmes -complets concernent un grand nombre de domaines différents : la biologie, avec par exemple l'algorithme de détermination de la séquence d'ADN qui correspond le mieux à un ensemble de fragmentsD. Gusfield. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press, 1997., ou le calcul de solutions optimales en économie, ou dans les processus de fabrication ou de transport.
Trouver un algorithme qui résout un problème -complet, comme le problème du voyageur de commerce, en temps polynomial suffirait à démontrer que , ce serait alors toute une série de problèmes très importants qui se trouveraient résolus (et, dans un même temps, si le polynôme est de degré petit, les systèmes de cryptographie à clé publique seraient cassés). Même sans exhiber un algorithme, une preuve pourrait donner des indices précieux pour construire un tel algorithme, ou pour le moins en relancer sérieusement la recherche, car on le saurait alors possible avec certitude. En admettant que les degrés des polynômes impliqués soient accessibles, l'existence de cet algorithme pourrait remettre en question l'utilisation des systèmes de cryptographie à clé publique, qui servent notamment pour la sécurisation des transactions bancaires. La sécurité repose sur l'assertion que ce n'est pas possible en temps polynomial.
Implications philosophiques sur la nature de la réflexion et de la créativité humaine Une implication de concerne le problème de la décision, nommé souvent sous le terme original allemand « Entscheidungsproblem ». Ce problème, posé par le mathématicien David Hilbert en 1928, consiste à se demander s'il existe un algorithme qui, si on lui présente une question mathématique dont la réponse est « Oui » ou « Non » dans un langage formel, trouvera automatiquement et infailliblement la réponse. Un tel algorithme serait potentiellement en mesure, par exemple, de répondre à la question de savoir si la conjecture de Goldbach ou l'hypothèse de Riemann est vraie ou fausse (si ces problèmes sont décidables).
Il a été démontré que le problème de la décision n'a pas de réponse dans le cas général, pour toutes les questions exprimables dans un langage formel donné. Cette démonstration a été apportée en 1936, indépendamment, par Alan Turing et Alonzo Church. Ils démontrent qu'il y a toujours des questions algorithmiquement indécidables, dont un algorithme ne peut trouver la réponse, dans tout système formel cohérent et suffisamment puissant pour exprimer des questions intéressantes.
Une implication considérable de la démonstration de serait qu'il deviendrait envisageable de résoudre une forme réduite du problème de la décision, c'est-à-dire pour les questions dont la démonstration est courte. La vérification de la validité d'une démonstration est un problème polynomial par rapport à la longueur de la démonstration N, ce qui veut dire qu'étant donné N, trouver une démonstration de longueur N est un problème de la classe , dont la complexité est a priori exponentielle par rapport à N, car il existe de l'ordre de démonstrations possibles de longueur N (C étant dépendant du langage formel employé). Une recherche par force brute de la démonstration donne donc une complexité exponentielle à l'algorithme.
Mais si , alors il doit être possible de faire mieux qu'une recherche par force brute, et il existe alors un algorithme de complexité polynomiale par rapport à N pour trouver la démonstration. Si, donc, on se limite aux démonstrations de longueur N, N étant suffisamment grand pour être raisonnablement sûr que la démonstration n'est pas plus grande, alors un algorithme résolvant les problèmes -complets serait en mesure, dans un temps polynomial par rapport à N, de trouver la démonstration valide parmi les démonstrations possibles de longueur N..
Un grand nombre de questions mathématiques pourraient être alors résolues, automatiquement, dont vraisemblablement d'autres problèmes du prix du millénaire6..
Plus philosophiquement, une démonstration mathématique peut être vue comme une codification d'un raisonnement humain plus généralParagraphe 1 : Significance.. Trouver un algorithme de démonstration automatique aurait des implications considérables pour tout ce qui concerne le raisonnement et la créativité humaine : il serait alors envisageable de laisser un ordinateur trouver des théories physiques, ou même composer de la musique, pour autant qu'un algorithme formel de vérification puisse être déterminé.
Implications de S'il est démontré que , il serait alors impossible de résoudre tous les cas des problèmes -complets dans un temps polynomial, et ces problèmes seraient alors hors de la classe des problèmes qui peuvent être traités de manière efficace.
Cela signifierait également qu'il est, fondamentalement, plus difficile de chercher la solution d'un problème que de vérifier qu'une réponse donnée a priori est effectivement une solution valable du problème.
Mais cette situation n'aurait pas que des inconvénients. La cryptographie à clé publique et la sécurité bancaire seraient assurées, mais plus encore : il est démontré que si , chaque problème (et non ) a alors une preuve à divulgation nulle de connaissance assurée et démontrée, ce qui rend de grands services en matière d'authentificationParagraphe 7.1..
Une preuve de serait également un approfondissement de la théorie de la complexité algorithmique : elle donnerait sans doute des réponses à la question de savoir « pourquoi » il est impossible de faire mieux que la force brute pour certains problèmes, et apporterait des pistes pour améliorer tout de même l'efficacité des algorithmes résolvant les problèmes -complets (sans les rendre polynomiaux pour autant, bien entendu) et pour démontrer plus formellement la sécurité des systèmes cryptographiques..
Cependant, il resterait à évaluer — sur le plan pratique — jusqu'à quel point les problèmes -complets pourraient être traités.
Problèmes intermédiaires Ladner a démontré que si , alors il existe des problèmes intermédiaires, ni -complet, ni dans ..
Temps moyen polynomial Stephen Cook fait remarquer qu'il reste possible qu'il existe un algorithme résolvant les problèmes -complets dans un temps polynomial, dans une majorité de cas de figure. Il serait alors possible de conjecturer, et peut-être prouver, une forme plus faible du problème , où la question serait de savoir s'il existe un algorithme pour résoudre dans un temps « en moyenne » polynomial, des problèmes -complets qui ont une distribution raisonnable de cas de figure.
Algorithmes exponentiels rapides Des algorithmes exponentiels rapides peuvent être plus efficaces en pratique que des algorithmes polynomiaux, pour une taille du problème restreinte correspondant à des cas pratiques. Par exemple, un algorithme en peut être plus efficace en pratique qu'un algorithme en Introduction..