Voir la source de Problème P ≟ NP

[[Fichier: P_np_fr.svg|vignette|400px|Représentation visuelle des deux configurations possibles.]]

Le '''problème {{math|P ≟ NP}}''' 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]]<ref>{{en}} [http://www.claymath.org/millennium-problems/p-vs-np-problem], sur le site de l'Institut Clay.</ref>, et offre à ce titre un million de [[Dollar américain|dollars]] à quiconque sera en mesure de démontrer {{math|1=P = NP}} ou {{math|P ≠ NP}} ou de démontrer que ce n'est pas démontrable. Ce problème est également le troisième [[problèmes de Smale|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 [[P (complexité)|complexité {{math|P}}]] des [[Problème de décision|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 [[NP (complexité)|complexité {{math|NP}}]] 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 [[fonction exponentielle|exponentiel]] par exemple).

À condition que le degré du [[polynôme]] issu du caractère polynomial de l'algorithme soit raisonnable, les conséquences de {{math|1=P = NP}} pourraient être considérables dans de nombreux domaines : [[cryptologie]], [[informatique]], [[mathématiques]], [[ingénierie]], [[économie (discipline)|économie]]. S'il était prouvé que {{math|1=P = NP}}, alors la résolution de tous les autres problèmes posés par l’Institut Clay pourrait devenir évidente<ref group="Fort" name=egal>Paragraphe « What if "P=NP"? ».</ref>{{,}}<ref group="Coo">p. 6</ref>. S'il était au contraire avéré que {{math|P ≠ NP}}, 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 {{math|P ≟ NP}} est présenté par l'Institut Clay<ref>[http://www.claymath.org/millennium-problems/p-vs-np-problem P vs NP] sur le site du [http://www.claymath.org/ Clay Mathematics Institute].</ref>.

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 [[Logement_étudiant_en_France#Les_résidences_universitaires|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 {{math|NP}}. 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 {{math|P}} (facile à trouver) vis-à-vis de {{math|NP}} (facile à vérifier) en 1971.

== Complexité des algorithmes, classes {{math|P}} et {{math|NP}} ==
{{loupe|Théorie de la complexité (informatique théorique)}}
<!-- rappels sur ces notions, pour que l'article soit auto-suffisant. Je ferai ce paragraphe en dernier. Appel au peuple si quelqu'un se sent pour faire ce paragraphe ;) -->

== Importance et implications de {{math|1=P = NP}} ==
Un des aspects essentiels de ce problème provient du fait qu'il existe une classe de problèmes très importants dits « [[NP-complet|{{math|NP}}-complets]] » qui est la sous-classe de {{math|NP}} dont les problèmes sont au moins aussi durs que tous les problèmes de {{math|NP}}, autrement dit les problèmes les plus durs de {{math|NP}}. 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 {{math|NP}}-complets) et, d'autre part, par définition de la {{math|NP}}-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 {{math|NP}}-complets, et plus généralement ''tous'' les problèmes {{math|NP}}. Le [[théorème de Cook]] montre que le [[problème SAT]] est {{math|NP}}-complet<ref>[[Leonid Levin]] avait pris comme point de départ un problème de pavage.</ref>, ce résultat a ensuite été largement réutilisé pour établir une [[liste de problèmes NP-complets|liste de problèmes {{math|NP}}-complets]].

Les problèmes {{math|NP}}-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 fragments<ref>D. Gusfield. ''Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology''. Cambridge University Press, 1997.</ref>, ou le calcul de solutions optimales en économie, ou dans les processus de fabrication ou de transport<ref group="Fort" name=egal/>.

Trouver un algorithme qui résout un problème {{math|NP}}-complet, comme le [[problème du voyageur de commerce]], en temps polynomial suffirait à démontrer que {{math|1=P = NP}}, 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 {{math|1=P = NP}} 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écidable]]s).

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écidable]]s, 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 {{math|1=P = NP}} 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 {{math|NP}}, dont la complexité est ''a priori'' exponentielle par rapport à N, car il existe de l'ordre de <math>C^N</math> démonstrations possibles de longueur ''N'' (''C'' étant dépendant du langage formel employé). Une recherche par [[Attaque par force brute|force brute]] de la démonstration donne donc une complexité exponentielle à l'algorithme.

Mais si {{math|1=P = NP}}, 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 {{math|NP}}-complets serait en mesure, dans un temps polynomial par rapport à ''N'', de trouver la démonstration valide parmi les <math>C^N</math> démonstrations possibles de longueur ''N''<ref group="Del">{{p.|92}}.</ref>.

Un grand nombre de questions mathématiques pourraient être alors résolues, automatiquement, dont vraisemblablement d'autres [[problèmes du prix du millénaire]]<ref group="Coo" name="cookp9">{{p.}}6.</ref>.

Plus philosophiquement, une démonstration mathématique peut être vue comme une codification d'un raisonnement humain plus général<ref group="Sip">Paragraphe 1 : Significance.</ref>. 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é<ref group="Coo" name="cookp9"/>.

== Implications de {{math|P ≠ NP}} ==
S'il est démontré que {{math|P ≠ NP}}, il serait alors impossible de résoudre tous les cas des problèmes {{math|NP}}-complets dans un temps polynomial, et ces problèmes seraient alors hors de la classe des problèmes qui peuvent être traités {{incise|théoriquement}} 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 {{math|P ≠ NP}}, chaque problème {{math|NP}} (et non {{math|P}}) a alors une [[preuve à divulgation nulle de connaissance]] assurée et démontrée, ce qui rend de grands services en matière d'[[authentification]]<ref group="Fort">Paragraphe 7.1.</ref>.

Une preuve de {{math|P ≠ NP}} 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 {{math|NP}}-complets (sans les rendre polynomiaux pour autant, bien entendu) et pour démontrer plus formellement la sécurité des systèmes cryptographiques<ref>[http://rjlipton.wordpress.com/2010/08/18/proofs-proofs-who-needs-proofs/ Proofs, Proofs, Who Needs Proofs?].</ref>.

Cependant, il resterait à évaluer — sur le plan pratique — jusqu'à quel point les problèmes {{math|NP}}-complets pourraient être traités.

=== Problèmes intermédiaires ===
Ladner a démontré que si {{math|P ≠ NP}}, alors il existe des [[NP-intermédiaire|problèmes intermédiaires]], ni {{math|NP}}-complet, ni dans {{math|P}}<ref>{{Article |auteur1=[[Richard E. Ladner]] |titre=On the Structure of Polynomial Time Reducibility |périodique=[[Journal of the ACM]]|volume=22 |numéro=1 |date=janvier 1975|doi=10.1145/321864.321877 |lire en ligne=http://doi.acm.org/10.1145/321864.321877 |consulté le=2017-07-16 |pages=155–171 }}.</ref>.

=== Temps moyen polynomial ===
[[Stephen Cook]] fait remarquer qu'il reste possible qu'il existe un algorithme résolvant les problèmes [[NP-complet|{{math|NP}}-complets]] dans un temps polynomial, dans une majorité de cas de figure<ref group="Coo" name="cookp9"/>. Il serait alors possible de conjecturer, et peut-être prouver, une forme plus faible du problème {{math|P ≟ NP}}, où la question serait de savoir s'il existe un algorithme pour résoudre dans un temps « en moyenne » polynomial, des problèmes {{math|NP}}-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 <math>O \left( 1{,}01^n \right)</math> peut être plus efficace en pratique qu'un algorithme en <math>O \left( n^4 \right)</math><ref group="Woe" name="Intro">Introduction.</ref>.

L'utilisation d'[[algorithme probabiliste|algorithmes probabilistes]] permet d'obtenir des algorithmes exponentiels plus rapides, pour certains problèmes, que les algorithmes déterministes. Par exemple, pour le [[problème SAT]], l'algorithme déterministe le plus rapide est en <math>O \left( 1{,}4726^n \right)</math>, alors que l'algorithme probabiliste le plus rapide est en <math>O \left( 1{,}3222^n \right)</math><ref>[[Rajeev Motwani]] and P. Raghavan [http://penguin.ewu.edu/cscd501/Wint-2009/Probabilistic/p33-motwani.pdf Improving Deterministic and Randomized Exponential-Time Algorithms].</ref>.

Dans le même ordre d'idées, la puissance absolue des ordinateurs permet, même avec un algorithme exponentiel, de trouver en pratique la solution pour des problèmes {{math|NP}}-complets pour tous les cas se présentant dans la vie courante : ainsi il est possible de résoudre le [[problème du voyageur de commerce]] pour des voyages allant jusqu'à {{Unité|2000 villes}}<ref group="Woe" name="Intro"/>.

Toutefois, ces algorithmes exponentiels rapides ne permettent pas de remettre en cause la sécurité des algorithmes de cryptographie ou d'authentification par exemple, dans la mesure où la taille du problème peut être artificiellement et arbitrairement augmentée de manière à se trouver hors d'atteinte de la puissance brute des ordinateurs.

=== Algorithmes sous-exponentiels ===
Même si {{math|P ≠ NP}}, il reste possible (le contraire n'a pas été démontré) qu'il existe des algorithmes sous-exponentiels pour résoudre les problèmes {{math|NP}}-complets<ref group="Woe" name="P7">Paragraphe 7.</ref>. Un algorithme est sous-exponentiel si le [[logarithme]] du temps d'exécution croît asymptotiquement moins vite que tout polynôme donné. Par exemple un algorithme en <math>O \left( 2^{n^\epsilon} \right) </math> avec <math>\epsilon < 1</math>, ou <math>O \left(n^{\log(n)}\right) </math> serait sous-exponentiel. La classe des problèmes sous-exponentiels est notée {{math|SUBEXP}}. Jusqu'à présent, aucun algorithme de ce genre n'a été exhibé pour des problèmes démontrés {{math|NP}}-complets, mais il en existe pour des problèmes {{math|NP}} comme la [[décomposition en facteurs premiers]] (voir [[crible algébrique]]) ou le [[problème de l'isomorphisme de graphes]]<ref>Cependant un résultat récent de László Babai démontre la complexité quasi-exponentielle de ce problème. Voir [https://arxiv.org/abs/1512.03547 László Babai ''Graph Isomorphism in Quasipolynomial Time''] sur ArXiV.org.</ref>, dont on ne sait pas s'ils sont NP-complets ou non.

Il existe cependant des conjectures qui sont reconnues comme probablement vraies, concernant l'existence d'algorithmes sous-exponentiels<ref group="Woe" name="P7"/>. Il existe une classe de problèmes {{math|SNP}} (Strict NP)<ref>[[Christos Papadimitriou|C. H. Papadimitriou]] et M. Yannakakis ''Optimization, approximation, and complexity classes'', ''Journal of Computer and System Science 43'', {{pp.|425-440}}, 1991.</ref> qui regroupe la plupart des problèmes {{math|NP}} importants. On considère probable que <math>\text{SNP} \nsubseteq \text{SUBEXP}</math>, c'est-à-dire qu'un certain nombre de problèmes {{math|SNP}} ne possèdent pas d'algorithmes sous-exponentiels<ref group="Woe" name="P7"/>.

Si cette conjecture est vraie, alors il est démontré que le problème {{math|NP}}-complet de [[Problème SAT|k-satisfaisabilité]], avec <math>k \geq 3</math>, ne peut être résolu par un algorithme sous-exponentiel, et par conséquent il en serait de même pour tous les problèmes {{math|NP}}-complets<ref group="Woe" name="P7"/> (par réduction).

=== Démonstrations non constructives d'existence d'algorithmes polynomiaux ===
Le [[théorème de Robertson-Seymour]] (démontré en 2004) permet de montrer l'existence d'algorithmes rapides (polynomiaux, et même cubiques) de résolution de sous-problèmes dont on sait que le cas général est [[Problème NP-complet|{{math|NP}}-complet]], voire [[Théorie de la complexité des algorithmes#Problèmes C-complets ou C-difficiles|{{math|NP}}-difficile]]<ref>Voir en ligne le cours de Jeff Erickson {{lien archive|langue=en|consulté le=2013-04-14|url=http://compgeom.cs.uiuc.edu/~jeffe/teaching/comptop/notes/graph-minors.pdf|titre= ''Computational Topology''|passage=3, section 12 (''graph minors'')|format=pdf|auteur=Jeff Erickson|horodatage archive = 20100613190440}}.</ref>. Ainsi, le problème des chemins disjoints, lequel consiste à déterminer, étant donné ''n'' paires de sommets, s'il existe dans le graphe ''n'' chemins disjoints les reliant deux à deux, est {{math|NP}}-complet ; le problème reste même {{math|NP}}-complet pour des graphes assez simples<ref>{{lien brisé|langue=en|consulté le=2013-04-14|url=http://www.nishizeki.ecei.tohoku.ac.jp/nszk/nishi/sub/j/DVD/PDF_J/J137.pdf|titre=Comme cela fut démontré en 2001 par Nishizegi, Vigen et Zhou}}.</ref>, mais Robertson et Seymour ont montré que, à ''k'' fixé, le problème des ''k'' chemins disjoints est effectivement soluble en temps polynomial<ref>{{article
  |langue=en
 | nom1 = Robertson | prénom1 = Neil
 | nom2 = Seymour | prénom2 = Paul
 | doi = 10.1006/jctb.1995.1006
 | numéro = 1
 | journal=[[Journal of Combinatorial Theory]], Series B
 | pages = 65–110
 | titre = Graph Minors. {{XIII}}. The disjoint paths problem
 | volume = 63
 | date = janvier 1995}}.</ref> ; cela ne prouve cependant pas que {{math|1=P = NP}}, car le temps pris par l'algorithme est un polynôme en ''n'' (la taille du graphe étudié) de la forme <math>C(k)n^3</math>, mais la constante <math>C(k)</math> augmente au moins exponentiellement avec ''k''. De plus, leur théorème ne donne aucun moyen effectif de construire l'algorithme en question (il repose sur la détermination préalable, pour chaque valeur de ''k'', d'un ensemble fixe de graphes, en nombre certes fini, mais qui peut être colossal).

Bien que le théorème de Robertson-Seymour n'ait pas vraiment apporté d'informations nouvelles concernant le problème {{math|P ≟ NP}}, Fellows et Langston ont fait remarquer<ref>{{article
  |langue=en
 | nom1 = Fellows | prénom1 = Michael R.
 | nom2 = Langston | prénom2 = Michael A.
 | numéro = 3
 | journal = [[Journal of Computer and System Sciences]]
 | pages = 769–779
 | titre = On search, decision, and the efficiency of polynomial-time algorithms
 | volume = 49
 | date = décembre 1994
 | doi = 10.1016/S0022-0000(05)80079-0}} ; en voici [http://www.mrfellows.net/papers/FL89_Search,Decision,Efficiency.pdf un résumé étendu] {{pdf}}, dû aux auteurs eux-mêmes.</ref> que leur démonstration non constructive d'existence d'algorithmes polynomiaux (et où apparaissent souvent, qui plus est, des constantes de proportionnalité bien trop grandes pour qu'ils puissent avoir une utilisation pratique quelconque) rend moins claire qu'auparavant la distinction entre algorithmes polynomiaux (considérés comme utilisables de manière réaliste) et non polynomiaux (à jamais inutilisables pour des ensembles de données un peu vastes), et donc que l'intuition de la majorité des informaticiens, selon laquelle la classe {{math|P}} est différente de la classe {{math|NP}}, pourrait bien se révéler fausse, sans pour autant que les problèmes {{math|NP}}-complets en deviennent faciles à résoudre.

== Position des théoriciens sur ce problème ==
Les théoriciens de la complexité algorithmique pensent en majorité que {{math|P ≠ NP}}. Dans une enquête réalisée par William Gasarch en 2002 auprès de 100 théoriciens de la question, 61 d'entre eux ont déclaré penser que {{math|P ≠ NP}}, alors que seuls 9 d'entre eux pensent que {{math|1=P = NP}}, 4 penchent plutôt pour l'indécidabilité (a priori dans {{math|ZFC}}) (mais 3, qui ne se prononcent pas, estiment qu'au contraire elle n'est même pas indépendante de l'{{lien|fr=arithmétique primitive récursive|trad=Primitive recursive arithmetic}}, une théorie bien plus faible) ;  les autres ne prennent pas position sur la question<ref>{{lien web|langue=en|url=http://www.cs.umd.edu/~gasarch/papers/poll.pdf |titre=The P=?NP poll. {{en}}|éditeur={{lien|SIGACT News}}|date=2002|auteur=William I. Gasarch}}.</ref>.

Les raisons de penser que {{math|P ≠ NP}} sont en effet assez nombreuses :

* Un argument qui revient souvent est que, sans a priori, si on défend l'idée que {{math|1=P = NP}}, on peut s'attendre à ce qu'un algorithme polynomial résolvant un problème {{math|NP}}-complet soit trouvable assez facilement, alors que, si on défend {{math|P ≠ NP}}, on s'attend à ce qu'il ne soit jamais trouvé. Le tableau de la situation, après plus de cinquante ans de recherches vaines en ce sens, est plus conforme et cohérent à {{math|P ≠ NP}}.

* Plus formellement, un article de Razborov et Rudich de [[1993]]<ref>A.A. Razborov, S. Rudich ''Natural proofs'' J. Comp. Sys. Sci. 55:24-35 1993 [http://www-2.cs.cmu.edu/~rudich/papers/natural.ps].</ref>, qualifié par [[Scott Aaronson]] d'un des résultats les plus importants concernant le problème {{math|1=P = NP}}, tend à démontrer que la raison pour laquelle {{math|P ≠ NP}} est si difficile à démontrer, est que probablement {{math|P ≠ NP}}<ref group="Aar">4. "Natural Proof".</ref>. Cet article montre une contradiction entre certaines conjectures très plausibles sur les [[Générateur de nombres pseudo-aléatoires|générateurs de nombres pseudo-aléatoires]] et les procédés habituels de démonstration de {{math|P ≠ NP}}, appelés [[preuve naturelle|preuves naturelles]]. Si {{math|P ≠ NP}} est démontrable, alors ce sera nécessairement avec des méthodes nouvelles, très différentes des méthodes habituellement employées dans les démonstrations.

* Un argument plus philosophique s'appuie sur la considération qu'un monde où {{math|1=P = NP}} est très différent d'un monde où {{math|P ≠ NP}}. Dans un monde où {{math|1=P = NP}}, des capacités jusqu'ici réservées aux êtres humains (créativité, recherche…) sont potentiellement accessibles au calcul<ref>[http://www.scottaaronson.com/blog/?p=122 10 Reasons to believe P ≠ NP] Blog de [[Scott Aaronson]].</ref>.

== Indécidabilité de {{math|P ≟ NP}} dans {{math|ZFC}} ==
Le fait qu'il soit très difficile de trouver une démonstration à {{math|1=P = NP}} ou {{math|P ≠ NP}} peut amener à envisager que ce problème soit [[indécidable]] (dans le système le plus couramment utilisé en mathématiques, à savoir le système formel {{math|[[ZFC]]}}). Un problème indécidable est un problème dont la véracité ou la fausseté n'admet aucune démonstration dans un [[système formel]] donné. On parle aussi d'« indépendance » du problème par rapport au système formel. Si un problème est indécidable, on peut alors le prendre ou prendre sa négation comme nouvel [[axiome]] pour forger un nouveau système formel plus large. L'inéluctabilité de propositions indécidables en arithmétique a été démontrée par [[Kurt Gödel|Gödel]] en [[1931]] par le célèbre [[Théorèmes d'incomplétude de Gödel|théorème d'incomplétude]].

Pendant longtemps, la majorité des mathématiciens a pensé que l'indécidabilité était réservée à des problèmes artificiels, spécialement conçus pour être indécidables, comme ceux que Gödel a construits pour démontrer son théorème. Cependant, depuis que l'[[hypothèse du continu]] a été démontrée indécidable par rapport au système formel {{math|ZFC}} en [[1963]], on sait que des problèmes mathématiques importants et  même fondamentaux peuvent être indécidables, et donc que leur véracité ou leur fausseté ne peut être établie ; à partir des années 1970, de nouveaux résultats en [[théorie de la démonstration]] ont permis de construire des problèmes naturels indécidables dans un système donné, comme l'exemple du [[théorème de Goodstein]].

Il n'est donc pas exclu que le problème {{math|P ≟ NP}} soit indécidable. Un certain nombre de résultats viennent étayer cette possibilité, bien que la communauté des théoriciens{{refnec}} pense en général que ce problème « n'est pas » indécidable dans ZFC (et continue par conséquent à en rechercher activement une démonstration).

=== Résultats en faveur de l'indécidabilité dans {{math|ZFC}} ===
R. DeMillo et R. Lipton ont démontré en [[1979]]<ref>R.A. DeMillo, R.J. Lipton, ''The consistency of P = NP and related problems with fragments of number theory'', in: Proceedings of the 12th Annual ACM Symposium on the Theory of Computing, 1980, {{pp.|45-57}}.</ref> que dans un certain système formel nommé {{math|EF}}, moins puissant que {{math|ZFC}}, mais suffisamment puissant pour démontrer beaucoup de problèmes mathématiques, le problème {{math|1=P = NP}} était indécidable. Malheureusement, {{math|EF}} a été artificiellement construit, et trop faible pour en tirer des conclusions significatives<ref group="Del">p. 93.</ref>. Toutefois, ce résultat vient confirmer que, pour démontrer {{math|1=P = NP}}, il faudra utiliser des axiomes, qui ne sont pas des théorèmes de {{math|EF}}.

En théorie de la complexité algorithmique, on utilise des [[Oracle (machine de Turing)|oracles]] qui invoquent des décisions hors de la complexité considérée. Par hypothèse, un oracle sait répondre instantanément à un problème déterminé (par exemple, la primalité d'un nombre ou le [[problème de l'arrêt]]). Pour chaque oracle <math>O</math>, il existe une classe de complexité <math>P_O</math>, <math>NP_O</math>, etc. correspondant aux problèmes qui peuvent être résolus ou vérifiés en temps polynomial, en invoquant cet oracle.

Avec certains oracles et dans un système formel donné ''F'', on peut démontrer que <math>P_O = NP_O</math>, et avec d'autres que <math>P_O \neq NP_O</math>. C'est un résultat auquel on peut s'attendre si le problème {{math|P ≟ NP}} est indécidable dans ''F'', car toute démonstration du problème sans oracle devra pouvoir s'adapter aux cas avec oracle et donner deux résultats différents, ce qui est a priori très difficile, voire impossible<ref group="Del" name="Del92">{{p.|92}}, encadré.</ref>. De plus, il a été démontré que le problème <math>P_O = NP_O</math> est indécidable avec certains oracles, dans {{math|ZFC}}<ref group="Aar">3.1 Oracles.</ref>, ce qui est considéré comme un argument en faveur de l'indécidabilité du problème<ref group="Del" name="Del92"/>. Il a été aussi démontré que si on choisit un oracle ''{{Précision nécessaire|au hasard|date=26-02-2017}}'' alors <math>P_O \neq NP_O</math> avec une probabilité de 1<ref>Herbert B. Enderton ''Computability Thoery'' Elsevier 2011, {{p.|148}}.</ref>.

=== Résultats en faveur de la décidabilité dans {{math|ZFC}} ===
Toutefois, [[Jean-Paul Delahaye]] fait également remarquer<ref>{{Logique, informatique et paradoxes|numéro chapitre=13|titre chapitre=IP=PSPACE}}.</ref> que cette situation disparate où, en fonction des oracles, on peut démontrer des résultats différents peut ne pas être significative, car la situation de la démonstration du problème {{math|1=[[IP (complexité)|IP]] = [[PSPACE]]}} était très similaire avant que [[Adi Shamir]] parvienne à démontrer que ces deux ensembles sont égaux à l'aide de techniques en fait très simples. Selon Delahaye, cet exemple donne des raisons d'espérer non seulement que le problème {{math|1=P = NP}} est décidable (dans {{math|ZFC}}), mais aussi que sa démonstration est à notre portée.

== Statut du problème par rapport à d'autres modèles de calcul ==

=== Informatique quantique ===
[[Image:BQP complexity class diagram.svg|vignette|Relations supposées entre la classe {{math|[[BQP]]}} et les autres classes de complexité<ref name="Nielsen Chuang 2000">{{Ouvrage | langue=en | langue originale=la | auteur1=Michael Nielsen | auteur2=Isaac Chuang | titre=Quantum Computation and Quantum Information | lieu=Cambridge | éditeur=[[Cambridge University Press]] | année=2000 | pages totales=676 | format livre=poche | isbn=978-0-521-63503-5 | oclc=174527496 | lire en ligne=https://books.google.com/books?id=aai-P4V9GJ8C&printsec=frontcover}}.</ref>.]]

La classe des problèmes qui peuvent être résolus efficacement par des [[calculateur quantique|calculateurs quantiques]] est appelée {{math|[[BQP]]}}, pour « Bounded error, Quantum, Polynomial time » (littéralement : Erreur bornée, Quantum, Temps polynomial), et constitue la contrepartie de la classe de complexité {{math|[[Formule BBP|BBP]]}} pour les ordinateurs classiques (les calculateurs quantiques exécutent uniquement des [[Algorithme probabiliste|algorithmes probabilistes]]). La classe {{math|BQP}} est la classe des problèmes qui peuvent être résolus par un calculateur quantique en temps polynomial, avec une probabilité d'erreur d'au plus 1/3.

{{math|BQP}} est supposé [[Disjonction logique|disjoint]] de la classe [[Problème NP-complet|{{math|NP}}-complet]], et un sur-ensemble de la classe {{math|P}} (voir schéma), mais cela n'est pas démontré. La [[décomposition en produit de facteurs premiers]] est un problème de classe NP (mais on ne sait pas s'il est {{math|NP}}-complet), et {{math|BQP}} car il peut être résolu en temps polynomial par un algorithme quantique : l'[[algorithme de Shor]]. On pourrait donc être tenté de penser qu'un calculateur quantique serait en mesure de résoudre un problème {{math|NP}}-complet dans un temps polynomial.

Mais cet exemple ne donne pas d'indice probant en ce sens, car il se pourrait aussi que le problème de la décomposition en facteurs premiers soit en fait de classe {{math|P}}<ref>À la manière du problème du [[test de primalité]], qui est {{math|NP}}, mais qui a été démontré en définitive dans {{math|P}}.</ref>, auquel cas l'algorithme de Shor n'apporterait rien par rapport à l'informatique classique. De plus, l'algorithme de Shor s'appuie lourdement sur la [[structure algébrique]] des nombres, ce qui n'est le cas d'aucun problème {{math|NP}}-complet connu. Mais comme il n'est pas démontré que {{math|BQP}} est disjoint de {{math|NP}}-complet, on ne peut non plus formellement écarter l'hypothèse que les problèmes {{math|NP}}-complets puissent être en théorie calculables par un ordinateur quantique en temps polynomial.

Toutefois, les théoriciens s'accordent pour penser que les algorithmes quantiques ne pourront résoudre les problèmes {{math|NP}}-complets en temps polynomial<ref group="Fort" name="fortnow8">Paragraphe 8.</ref>. Notamment, il existe un algorithme quantique qui s'applique aux problèmes {{math|NP}}-complets : l'[[algorithme de Grover]]<ref>{{chapitre|langue=en|auteur1=Lov K. Grover|titre=A fast quantum mechanical algorithm for database search|titre ouvrage=STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing|date=juillet 1996|passage=212–219|doi=10.1145/237814.237866|arxiv=quant-ph/9605043|s2cid=207198067}}.</ref>, qui apporte une amélioration quadratique (<math>2^{\frac n 2}</math> au lieu de <math>2^n</math>), mais qui reste néanmoins exponentiel. Il existe de forts indices selon lesquels on ne pourra pas aller plus loin en matière d'algorithme quantique<ref group="Fort" name="fortnow8"/>.

== Présentation formelle du problème utilisant des machines de Turing ==
Le problème {{math|P ≟ NP}} est « robuste » et peut être posé pour des modèles de calcul équivalents aux ordinateurs actuels (essentiellement des modèles de calcul déterministes qui se simulent entre eux en temps polynomial). La présentation qui suit reprend essentiellement celle donnée par [[Stephen Cook]] pour l'institut Clay<ref>Page de présentation du problème sur le site de l'institut clay [http://www.claymath.org/millennium-problems/p-vs-np-problem].</ref>, qui utilise des [[machine de Turing|machines de Turing déterministes]] à une bande infinie à droite, et dont l'ensemble des états contient en particulier deux états terminaux (la machine s'arrête quand elle est dans l'un de ces deux états), l'un acceptant et l'autre refusant.

On note <math>\Sigma^*</math> l'ensemble des mots sur l'alphabet <math>\Sigma</math>. La longueur d'un mot {{math|''w'' ∈ Σ<sup>*</sup>}} est notée |{{math|''w''}}|. La machine est supposée déterministe, c'est-à-dire qu'à une configuration de celle-ci, est associée une seule nouvelle configuration (éventuellement aucune), qui constitue une étape de calcul.
* On dit qu'un mot <math>w \in \Sigma^*</math> est reconnu par <math>M</math>, une machine de Turing, si l’exécution de <math>M</math> avec <math>w</math> en entrée se termine dans l'état acceptant en un nombre fini d'étapes (chaque étape correspond à une transition). Et on note <math>L_M</math> l'ensemble des mots de <math>\Sigma^*</math> reconnus par <math>M</math>.
* Pour tout mot <math>w\in\Sigma^*</math>, on définit <math>t_M(w)</math>, le nombre d'étapes au bout duquel la machine de Turing <math>M</math> avec entrée <math>w</math> s'arrête, c'est-à-dire se trouve dans un état terminal, ce nombre d'étapes, ou temps de calcul, est infini si la machine ne s'arrête pas pour cette entrée. Un langage (sur Σ) est un ensemble de mots, soit un sous-ensemble de {{math|Σ<sup>*</sup>}}. Un langage {{math|''L''}} est reconnu par une machine {{math|''M''}}, quand l'ensemble des mots reconnus par {{math|''M''}} est {{math|''L''}} (soit {{math|''L'' {{=}} ''L''(''M'')}}).
* On dit qu'une [[machine de Turing]] {{math|''M''}} fonctionne ''en temps polynomial'' s'il existe un entier ''k'' tel que pour tout entier ''n'' et tout mot ''w'' de longueur inférieure ou égale à ''n'' le temps de calcul de la machine pour cette entrée est borné par ''n''<sup>''k''</sup> : <math>\forall w\in\Sigma^\ast(|w|\leq n\Rightarrow t_M(w)\leq n^k)</math>.
* La classe {{math|P}} est l'ensemble des langages reconnus par une machine de Turing qui fonctionne en temps polynomial.
* À toute [[relation binaire]] <math>R</math> entre mots sur <math>\Sigma</math>, est associée un langage {{math|''L''<sub>''R''</sub>}} sur l'alphabet <math>\Sigma\cup\{/\}</math>, / étant un caractère de séparation n'appartenant pas à <math>\Sigma </math>, par <math>L_R=\{x/y|x\in\Sigma^*,y\in\Sigma^*, R(x,y)\}</math>. On dit que <math>R</math> est ''reconnue en temps polynomial'' si <math>L_R \in \mathrm P </math>.
* La classe {{math|NP}} est alors l'ensemble des langages {{math|''L''}} pour lesquels il existe un entier ''k'', et une relation {{math|''R''}} reconnue en temps polynomial, tel que pour tout {{math|''w''}},<br/><math>w\in L \Leftrightarrow \exists y (|y|<|w|^k~et~R(w,y))</math>.

Le problème {{math|P ≟ NP}} consiste à déterminer si les classes {{math|P}} et {{math|NP}} sont ou non égales.

== Dans la fiction ==
* Le film ''{{lien|trad=Travelling Salesman (2012 film)|Travelling Salesman}}'', réalisé en 2012 par Timothy Lanzone, raconte l'histoire de quatre mathématiciens engagés par le [[gouvernement des États-Unis]] pour résoudre le problème {{math|P ≟ NP}}<ref>{{lien web|langue=en|auteur1=Duncan Geere|titre='Travelling Salesman' movie considers the repercussions if P equals NP|périodique=[[Wired (magazine)|Wired]] UK|url=https://www.wired.co.uk/news/archive/2012-04/26/travelling-salesman|consulté le=26 avril 2012|date=2012-04-26}}.</ref>.
* Dans l'épisode 2 de la [[saison 2 d'Elementary|saison 2]] d'''[[Elementary (série télévisée)|Elementary]]'', diffusé en 2013, un meurtre vise deux mathématiciens s'approchant de la démonstration que {{math|1=P = NP}}, afin de pouvoir empocher une récompense d'un million de dollars offerte dans le cadre du [[Problèmes du prix du millénaire|problème du prix du millénaire]]<ref>{{lien web|date=11 décembre 2014|auteur1=[[Jean-Paul Delahaye]]|titre=P=NP : élémentaire, ma chère Watson ?|site=[[Interstices]]|url=https://interstices.info/pnp-elementaire-ma-chere-watson/}}.</ref>.
*Dans la bande dessinée ''Le Chercheur Fantôme'' par [[Robin Cousin]], publiée en 2013, un chercheur disparu prétend avoir résolu {{math|P ≟ NP}}.

== Bibliographie ==
* {{chapitre
| langue          = en
| prénom1         = Stephen A.| nom1   = Cook
| titre chapitre  = The Complexity of Theorem-Proving Procedures
| titre ouvrage   = Conference Record of Third Annual ACM [[Symposium on Theory of Computing]] (STOC)
| année           = 1971
| passage         = 151-158
| url texte       = http://4mhz.de/download.php?file=Cook1971_A4.pdf}}
* {{Reducibility Karp 1972}}
* {{Article
 | langue          = anglais
 | prénom1         = Lance
 | nom1            = Fortnow
 | lien auteur1    = :en:Lance Fortnow
 | titre           = The Status of the P Versus NP Problem
 | périodique      = [[Communications of the ACM]]
 | volume          = 52
 | numéro          = 9
 | date            = septembre 2009
 | pages           = 78-86
 | issn            = 0001-0782
 | url texte       = http://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext
 }} :
{{Références|groupe="Fort"}}
* [[Stephen Cook]] [http://www.claymath.org/sites/default/files/pvsnp.pdf The P versus NP problem.] « Official Problem description » du [[Clay Mathematics Institute]] :
{{Références|group="Coo"}}
* [[Michael Sipser]] ''[http://www.cs.bris.ac.uk/Teaching/Resources/COMS30126/sipser92history.pdf The History and Status of the P versus NP Question]'':
{{Références|group="Sip"}}
* {{chapitre|langue=en|auteur=[[Scott Aaronson]]|année=2016|éditeur=Springer|titre=P ≟ NP|titre ouvrage=Open Problems in Mathematics|passage=1-122|isbn=978-3-319-32160-8|url=http://www.scottaaronson.com/papers/pnp.pdf}}
* {{article|langue=en|auteur1=Scott Aaronson|date=octobre 2003|titre=Is P Versus NP Formally Independent?|revue=Bulletin of the EATCS|volume=81|url=http://www.scottaaronson.com/papers/indep.pdf}}<!-- http://people.cs.uchicago.edu/~fortnow/beatcs/column81.pdf -->
{{Références|group="Aar"}}
* [[Gerhard Woeginger]] ''[http://www.win.tue.nl/~gwoegi/papers/exact.pdf Exact algorithms for NP-hard problems: A survey]'' :
{{Références|group="Woe"}}
* {{Article
 | auteur1         = [[Jean-Paul Delahaye]]
 | titre           = Un algorithme à un million de dollars ?
 | périodique      = [[Pour la science]]
 | numéro          = 334
 | date            = août 2005
 | pages           = 90-95
 | url texte       = http://www.lifl.fr/~jdelahay/pls/2005/132.pdf
 }} :
{{Références|group="Del"}}
* C. H. Papadimitriou, "NP-completeness : a retrospective", appeared in ''ICALP 97'', Springer.
* {{Computational Complexity (Papadimitriou)}}

== Références ==
{{Références}}

== Voir aussi ==

=== Article connexe ===
* [[Théorème de Ladner]]
* [[21 problèmes NP-complets de Karp|21 problèmes {{math|NP}}-complets de Karp]]
* [[Francisco Dória]] et {{Lien|langue=en|fr=Newton da Costa}} pour leur « formalisation exotique »

=== Lien externe ===
* {{lien web |langue=en| url = http://www.win.tue.nl/~gwoegi/P-versus-NP.htm | titre = The P-versus-NP page |auteur = G. J. Woeginger}}. Nombreuses ressources sur le problème, ainsi qu'une centaine d'articles prétendant résoudre le problème.

{{Palette Problèmes du prix du millénaire}}
{{Portail|Logique|Informatique théorique}}

{{DEFAULTSORT:np}}
[[Catégorie:Problèmes du prix du millénaire]]
[[Catégorie:Conjecture non résolue]]
[[Catégorie:Théorie de la complexité des algorithmes]]
[[Catégorie:Problème mathématique]]