Problème P = NP

Représentation visuelle des deux configurations possibles.

En mathématiques, et plus précisément en informatique théorique, le problème $P = NP$ est un problème non résolu, et est considéré par de nombreux chercheurs comme un des plus importants problèmes 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 7 problèmes du prix du millénaire^[1], et offre à ce titre 1 000 000 $ à quiconque sera en mesure de prouver $P = NP$ ou $P \neq NP$ . 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.

Il s'agit plus formellement de savoir si la classe de complexité $P$ 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é $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 exponentiel par exemple).

Les conséquences de $P = NP$ pourraient être considérables dans de nombreux domaines : cryptologie, informatique, mathématiques, ingénierie, économie. On pourrait même imaginer que celui qui prouverait $P = NP$ ressortirait de l'Institut de mathématiques Clay avec 6 millions de dollars, les implications de la solution pouvant rendre la résolution des autres problèmes du millénaire triviale^{[Fortnow 1]}. S'il est au contraire avéré que $P \neq NP$ , cela signifierait qu'une large classe de problèmes sont presque sûrement définitivement hors d'atteinte du calcul dans un temps raisonnable (ou nécessite le développement d'architectures différentes de celles des machines de Turing).

Complexité des algorithmes, classes P et NP

Article détaillé : Théorie de la complexité des algorithmes.

Importance et implications de 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-complets » qui est la sous-classe de $NP$ dont les problèmes sont au moins aussi durs que tous les problèmes de $NP$ , autrement dit les problèmes les plus durs de $NP$ . Ils sont importants à double titre : d'une part, ils possèdent souvent une importance intrinsèque (de nombreux problèmes fondamentaux dans plusieurs domaines étant $NP$ -complets) et, d'autre part, par définition de la $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 tous les problèmes $NP$ -complets, et $NP$ en général en temps polynomial. Le théorème de Cook montre que le problème SAT est $NP$ -complet, ce résultat a ensuite été largement réutilisé pour établir une liste de problèmes NP-complets.

Les problèmes $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^[2], ou le calcul de solution optimales en économie (équilibres de Nash), ou dans les processus de fabrication ou de transport^{[Fortnow 1]}.

Trouver un algorithme qui résout un problème $NP$ -complet, comme le problème du voyageur de commerce, en temps polynomial suffirait à démontrer que $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, 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. L'existence de cet algorithme remettrait en question l'utilisation des systèmes de cryptographie à clé publique, qui servent notamment pour la sécurisation des transactions bancaires. En effet, casser ces systèmes revient à résoudre un problème NP (intuitivement, c'est facile si on connaît la clé privée). 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 autre implication considérable de la démonstration de $P=NP$ serait qu'il deviendrait envisageable de résoudre une forme réduite du problème de la décision, nommé souvent sous le terme original de 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 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.

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.

Cependant, il serait possible de résoudre en grande partie le problème de la décision 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. Étant donné N, trouver une démonstration de longueur N est donc un problème de classe $NP$ , dont la complexité est a priori exponentielle par rapport à N, car il existe de l'ordre de $C^N$ 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 $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 $NP$ -complet serait en mesure, dans un temps polynomial par rapport à N, de trouver la démonstration valide parmi les $C^N$ démonstrations possibles de longueur N^[3].

Un grand nombre de questions mathématiques pourraient être alors résolues, automatiquement, dont vraisemblablement d'autres problèmes du prix du millénaire^{[cook 1]}.

Plus philosophiquement, une preuve mathématique peut être vue comme une codification d'un raisonnement humain plus général^{[sipser 1]}. 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é^{[cook 1]}.

Implications de P ≠ NP

S'il est démontré que $P \neq NP$ , il serait alors impossible de résoudre tous les cas des problèmes NP-complets dans un temps polynomial, et ces problèmes seraient alors hors de la classe des problèmes qui peuvent être traités — 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 cette solution.

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 $P \neq NP$ , chaque problème NP (et non 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^{[Fortnow 2]}.

Une preuve de $P \neq 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 $NP$ -complets (sans les rendre polynomiaux pour autant, bien entendu) et pour démontrer plus formellement la sécurité des systèmes cryptographiques^[4].

Cependant, il resterait à évaluer - sur le plan pratique - jusqu'à quel point les problèmes NP-complets pourraient être traités :

Temps moyen polynomial

Stephen Cook fait remarquer qu'il reste possible qu'il existe un algorithme résolvant les problèmes NP-complets dans un temps polynomial, dans une majorité de cas de figure^{[cook 1]}. Il serait alors possible de conjecturer, et peut-être prouver, une forme plus faible du problème 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 $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 $O \left( 1,01^n \right)$ peut être plus efficace en pratique qu'un algorithme en $O \left( n^4 \right)$ ^{[Woeginger 1]}.

L'utilisation d'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 $O \left( 1,4726^n \right)$ , alors que l'algorithme probabiliste le plus rapide est en $O \left( 1,3222^n \right)$ ^[5].

Dans le même ordre d'idée, la puissance absolue des ordinateurs permet, même avec un algorithme exponentiel, de trouver en pratique la solution pour des problèmes 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'à 2000 villes^{[Woeginger 1]}.

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 $P \neq 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 NP-complets^{[Woeginger 2]}. 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 $O \left( 2^{n^\epsilon} \right)$ avec $\epsilon < 1$ , ou $O \left(n^{\log(n)}\right)$ serait sous-exponentiel. La classe des problèmes sous-exponentiels est notée $SUBEXP$ . Jusqu'à présent, aucun algorithme de ce genre n'a été exhibé pour des problèmes démontrés NP-complets, mais il en existe pour des problèmes NP comme la décomposition en facteurs premiers (voir crible algébrique) ou le problème de l'isomorphisme de graphes, 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^{[Woeginger 2]}. Il existe une classe de problèmes $SNP$ (Strict NP)^[6] qui regroupe la plupart des problèmes NP importants. On considère probable que $\text{SNP} \nsubseteq \text{SUBEXP}$ , c'est-à-dire qu'un certain nombre de problèmes SNP ne possèdent pas d'algorithmes sous-exponentiels^{[Woeginger 2]}.

Si cette conjecture est vraie, alors il est démontré que le problème NP-complet de k-satisfaisabilité, avec k >= 3, 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 NP-complets^{[Woeginger 2]}.

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 NP-complet, voire NP-difficile^[7]. 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 NP-complet ; le problème reste même NP-complet pour des graphes assez simples^[8], mais Robertson et Seymour ont montré que, à k fixé, le problème des k chemins disjoints est effectivement soluble en temps polynomial^[9] ; cela ne prouve cependant pas que P = NP, car le temps pris par l'algorithme est un polynôme en n (la taille du graphe étudié) de la forme $C(k)n^3$ , mais la constante $C(k)$ 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 P=NP, Fellows et Langston ont fait remarquer^[10] 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 P est différente de la classe NP, pourrait bien se révéler fausse, sans pour autant que les problèmes 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 $P \neq NP$ . Dans une enquête réalisée en 2002 auprès de 100 théoriciens de la question, 61 d'entre-eux ont déclaré penser que $P \neq NP$ , alors que seul 9 d'entre-eux pensent que $P=NP$ , les 30 restants ne souhaitant pas prendre position sur la question, ou penchant plutôt pour l'indécidabilité^[11]. C'est d'ailleurs ce relatif consensus qui justifie l'emploi de la cryptographie à clé publique pour sécuriser les transactions bancaires.

Les raisons de le penser sont en effet assez nombreuses :

Un argument qui revient souvent est que, sans a priori, si on défend l'idée que $P=NP$ , on peut s'attendre à ce qu'un algorithme polynomial résolvant un problème $NP$ -complet soit trouvable assez facilement, alors que, si on défend $P \neq 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 à $P \neq NP$ .

Plus formellement, un article de Razborov et Rudich de 1993^[12], qualifié par Scott Aaronson d'un des résultats les plus importants concernant le problème $P=NP$ , tend à démontrer que la raison pour laquelle $P \neq NP$ est si difficile à démontrer, est que probablement $P \neq NP$ ^{[aaronson 1]}. Cet article montre une contradiction entre certaines conjectures très plausibles sur les générateurs de nombres pseudo-aléatoires et les procédés habituels de démonstration de $P \neq NP$ . Si $P \neq 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 est de considérer qu'un monde où $P=NP$ est très différent d'un monde où $P \neq NP$ . Dans un monde où $P=NP$ , des capacités jusqu'ici réservées aux êtres humains (créativité, recherche…) sont potentiellement accessibles au calcul^[13].

Indécidabilité de P=NP

Le fait qu'il soit très difficile de trouver une démonstration à $P = NP$ ou $P \neq NP$ peut amener à envisager que ce problème soit indécidable. Un problème indécidable est un problème dont la vérité ou la fausseté n'admet aucune démonstration dans un système formel donné. Dit autrement, la vérité ou la fausseté sont toutes deux compatibles et cohérentes avec le système formel. On parle alors d'indépendance du problème par rapport au système formel. Il est alors possible de prendre librement la vérité ou bien la fausseté du problème comme nouvel axiome et l'ajouter aux axiomes du système formel pour forger un nouveau système formel. L'existence de telles propositions a été démontrée par Gödel en 1931 par le célèbre théorème d'incomplétude de Gödel.

Pendant longtemps, on a pensé que l'indécidabilité était réservée à des problèmes artificiels, spécialement conçus pour être indécidables. Cependant, depuis que l'hypothèse du continu a été démontrée indécidable par rapport au système formel ZFC en 1963, on sait que des problèmes mathématiques importants et fondamentaux peuvent être indécidables, et donc que leur vérité ou leur fausseté ne peut être établie.

Il n'est donc pas exclu que le problème $P = NP$ soit indécidable, et que toute démonstration en soit impossible dans le système formel ZFC utilisé par les mathématiciens. Un certain nombre de résultats viennent étayer cette possibilité, bien que la communauté des théoriciens pense en général que ce problème n'est pas indécidable (et continue par conséquent à en rechercher activement une démonstration).

Résultats en faveur de l'indécidabilité

R. DeMillo et R. Lipton ont démontré en 1979^[14] que dans un certain système formel nommé $EF$ , moins puissant que $ZFC$ , mais suffisamment puissant pour démontrer beaucoup de problèmes mathématiques, le problème $P = NP$ était indécidable. Malheureusement, $EF$ a été artificiellement construit, et trop faible pour en tirer des conclusions significatives^[3]. Toutefois, ce résultat vient confirmer que, pour démontrer ce problème, il faudra mettre en œuvre des techniques de démonstrations inhabituelles, qui ne peuvent être employées dans $EF$ .

Autre résultat : en théorie de la complexité algorithmique, on utilise la notion d'Oracle pour étudier un problème en s'affranchissant d'une autre problématique, considérée comme extérieure au problème étudié. Par hypothèse, un Oracle saura répondre à un problème déterminé (par exemple, un nombre est-il premier ou non, ou bien le problème de l'arrêt) instantanément. Pour chaque Oracle, il existe les classes de complexité $P_O$ , $NP_O$ , etc.. correspondantes aux problèmes qui peuvent être résolus ou vérifiés en temps polynomial, à l'aide de cet Oracle.

Avec certains Oracles, on peut prouver que $P_O = NP_O$ , et avec d'autres que $P_O \neq NP_O$ . C'est un résultat auquel on peut s'attendre si le problème $P = NP$ est indécidable, car toute preuve du problème sans Oracle devra pouvoir s'adapter aux cas avec Oracle et donner ces deux résultats différents, ce qui est a priori très difficile, voire impossible^[3]. De plus, il a été prouvé que le problème $P_O = NP_O$ est indécidable avec certains Oracles, dans $ZFC$ , ce qui est considéré comme significatif en faveur de l'indécidabilité du problème^{[aaronson 2]}. Il a été aussi démontré que si on choisit un oracle au hasard, alors $P_O \neq NP_O$ avec une probabilité de 1^[15].

Résultats en faveur de la décidabilité

Toutefois, Jean-Paul Delahaye fait également remarquer^[16] 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 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 $P = NP$ est décidable, mais aussi que sa démonstration soit à notre portée.

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

Informatique quantique

Relations supposées entre la classe BQP et les autres classes de complexité^[17].

La classe des problèmes qui peuvent être résolus efficacement par des calculateurs quantiques est appelée BQP, pour « Bounded error, Quantum, Polynomial time » (littéralement : Erreur bornée, Quantum, Temps polynomial), et constitue la contrepartie de la classe de complexité BBP pour les ordinateurs classiques (les calculateurs quantiques exécutent uniquement des algorithmes probabilistes). La classe $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.

$BQP$ est supposé disjoint de la classe NP-complet, et un sur-ensemble de la classe $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 $NP$ -complet), et $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 NP-complet dans un temps polynomial.

Mais cet exemple ne donne pas d'indice édifiant en ce sens, car il se pourrait aussi que le problème de la décomposition en facteurs premier soit en fait de classe $P$ ^[18], 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 $NP$ -complet connu. Mais comme il n'est pas démontré que $BQP$ est disjoint de $NP$ -complet, on ne peut non plus formellement écarter l'hypothèse que les problèmes $NP$ -complets puissent être en théorie calculable 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 $NP$ -complet en temps polynomial^{[Fortnow 3]}. Notamment, il existe un algorithme quantique qui s'applique aux problèmes $NP$ -complet : l'algorithme de Grover^[19], qui apporte une amélioration quadratique ( $2^{\frac n 2}$ au lieu de $2^n$ ), 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^{[Fortnow 3]}.

Enfin, il convient de remarquer que les calculateurs quantiques sont un type particulier de machines de Turing^{[réf. souhaitée]}. La thèse de Church s'applique donc a priori aux calculateurs quantiques, qui possèdent donc les mêmes propriétés et limitations théoriques que les ordinateurs classiques. Il n'y a donc pas lieu de penser, a priori, que le problème $P=NP$ puisse être fondamentalement différent dans le cas des calculateurs quantiques.

Présentation formelle du problème

Soit M= $(Q,\Gamma, B, \Sigma, q_0,q_y,q_n,\delta)$ une machine de Turing déterministe, dont les états finaux sont $q_y$ et $q_n$ .

On note $\Sigma^*$ l'ensemble des mots sur l'alphabet $\Sigma$ .
On dit qu'un mot x est reconnu par M si l’exécution de M avec x en entrée se termine avec l'état $q_y$ en un nombre fini d'étapes.
On note $L_M=\{x\in\Sigma^*| x~ \text{est reconnu par}~ M\}$ .
Pour tout mot $x\in\Sigma^*$ , on définit $T_M(x)$ , le nombre d'étapes nécessaires avant l’arrêt de la machine de Turing M avec l'entrée x. (Éventuellement, $T_M(x)$ peut être infini.)
On dit qu'une machine de Turing M est polynomiale s'il existe un polynôme P tel que $\forall n\in\mathbb{N}^*, max\{T_M(x),x\in \Sigma^n\}\le P(n)$
On définit $P$ comme l'ensemble de problèmes de décision (dont la réponse est oui ou non), tels qu'il existe une machine de Turing polynomiale qui le résout, ou de manière équivalente et plus formelle $P=\{L~(\subset \Sigma^*)| \exists M=(Q,\Gamma, B, \Sigma, q_0,q_y,q_n,\delta)\text{ machine de Turing polynomiale}, L=L_M\}$ .
(On associe en fait ici un problème de décision à l'ensemble de ses énoncés dans un certain codage, dont la réponse est oui)
On définit pour toute relation binaire $R$ entre mots de $\Sigma$ , $L_R=\{x.'/'.y|x\in\Sigma^*,y\in\Sigma^*, R(x,y)\}$ , où . est la concaténation et '/' un caractère de séparation n'appartenant pas à $\Sigma$ . On peut voir $R$ comme une relation qui à chaque énoncé x d'un problème de décision associe une ou plusieurs solutions, que la machine de Turing pourra vérifier.
On définit $NP=\{L~ (\subset \Sigma^*)| \exists R, L_R\in P\ | \exists k, \forall x\in \Sigma^*, x\in L \Leftrightarrow \exists y, (|y|<|x|^k~et~R(x,y)) \}$ .
NP peut de manière équivalente être défini comme l'ensemble de problèmes de décision pouvant se résoudre sur une machine de Turing non déterministe en un temps polynomial.

Le problème consiste à déterminer si $P$ et $NP$ sont égaux ou non au sens de la théorie des ensembles.

Bibliographie

(en) Lance Fortnow, « The Status of the P Versus NP Problem », Communications of the ACM, vol. 52, n^o 9,‎ septembre 2009, p. 78-86 (ISSN 0001-0782, lire en ligne) :

1 2 Paragraphe « What if "P=NP"? »
↑ Paragraphe 7.1
1 2 Paragraphe 8

Stephen Cook « The P versus NP problem. Official description. » ^{(Archive • Wikiwix • Archive.is • Google • Que faire ?)}, consulté le 2013-04-14:

1 2 3 page 9

Michael Sipser The History and Status of the P versus NP Question:

↑ Paragraphe 1 : Significance

Scott Aaronson Is P Versus NP Formally Independent? :

↑ 4. "Natural Proof"
↑ Paragraphe 3.1

Gerhard Woeginger Exact algorithms for NP-hard problems: A survey :

1 2 Introduction
1 2 3 4 Paragraphe 7

C. H. Papadimitriou, "NP-completeness : a retrospective", appeared in ICALP 97, Springer.
(en) Christos Papadimitriou, Computational Complexity, Addison-Wesley,‎ 1993 (ISBN 978-0-201-53082-7)

Références

↑ (en) P vs NP Problem, sur le site de l'Institut Clay
↑ D. Gusfield. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press, 1997.
1 2 3 Jean-Paul Delahaye « P=NP, un problème à un million de dollars ? » sur Interstices
↑ Proofs, Proofs, Who Needs Proofs?
↑ Rajeev Motwani and P. Raghavan Improving Deterministic and Randomized Exponential-Time Algorithms
↑ C.H. Papadimitriou et M. Yannakakis Optimization, approximation, and complexity classes Journal of Computer and System Science 43, pp. 425-440, 1991
↑ Voir en ligne« le cours de Jeff Erickson, Computational Topology, section 12 (graph minors), p. 3 » ^{(Archive • Wikiwix • Archive.is • Google • Que faire ?)}, consulté le 2013-04-14(en).
↑ « Comme cela fut démontré en 2001 par Nishizegi, Vigen et Zhou » ^{(Archive • Wikiwix • Archive.is • Google • Que faire ?)}, consulté le 2013-04-14 (en).
↑ (en) Neil Robertson et Paul Seymour, « Graph Minors. XIII. The disjoint paths problem », Journal of Combinatorial Theory, Series B, vol. 63, n^o 1,‎ 1995, p. 65–110 (DOI 10.1006/jctb.1995.1006).
↑ (en) Michael R. Fellows et Michael A. Langston, « On search, decision, and the efficiency of polynomial-time algorithms », Journal of Computer and System Sciences, vol. 49, n^o 3,‎ 1994, p. 769–779 ; en voici un résumé étendu [PDF], dû aux auteurs eux-mêmes.
↑ (en) William I. Gasarch, « The P=?NP poll. (en) », SIGACT News (en),‎ 2002
↑ A.A. Razborov, S. Rudich Natural proofs J. Comp. Sys. Sci. 55:24-35 1993
↑ 10 Reasons to believe P ≠ NP Blog de Scott Aaronson
↑ 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
↑ Herbert B. Enderton Computability Thoery Elsevier 2011, p. 148
↑ Jean-Paul Delahaye, Logique, informatique et paradoxes, Belin [détail des éditions], chap. 13 (« IP=PSPACE »)
↑ (en) Michael Nielsen and Isaac Chuang (trad. du latin), Quantum Computation and Quantum Information, Cambridge, Cambridge University Press,‎ 2000, poche (ISBN 978-0-521-63503-5, OCLC 174527496)
↑ À la manière du problème du test de primalité, qui est $NP$ , mais qui a été démontré en définitive dans $P$ .
↑ A fast quantum mechanical algorithm for database search

Voir aussi

Lien externe

(en) G. J. Woeginger, « The P-versus-NP page ». Nombreuses ressources sur le problème, ainsi qu'une centaine d'articles prétendant résoudre le problème.

Article connexe

Théorème de Ladner (de)

Portail de la logique
Portail de l'informatique théorique

This article is issued from Wikipédia - version of the Thursday, October 29, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.