Problème P = NP

La relation entre la classe des algorithmes de complexité P et la classe des algorithmes de complexité NP est un problème non résolu en informatique théorique, 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. À ce titre, l'Institut de mathématiques Clay, qui se consacre au développement et la diffusion des connaissances mathématiques, a inclus ce problème dans sa liste des problèmes du prix du millénaire.

Ce problème est souvent désigné comme le problème P = NP, car le problème est de savoir si ces deux classes sont équivalentes ou non. Les algorithmes de classe P sont les algorithmes dont le temps de traitement peut être majoré par un polynôme, en fonction du nombre d'éléments à traiter (par exemple T(N) = N). Les algorithmes de classe NP sont des algorithmes dont la vérification du résultat, une fois celui-ci connu, demande un temps polynomial.

En théorie de la complexité des algorithmes, un algorithme qui demande un temps d'exécution polynomial est considéré comme « rapide » (par rapport à un temps d'exécution exponentiel par exemple). Si la relation P=NP était démontrée, cela signifierait que si la solution d'un problème peut être vérifiée « rapidement », alors elle doit être nécessairement calculable « rapidement ». On saurait alors que de nombreux algorithmes importants peuvent être accélérés de manière drastique. Les conséquences en seraient considérables dans de nombreux domaines : cryptologie, informatique, mathématiques, ingénierie, économie…

S'il est avéré que P n'est pas égal à NP, cela signifierait que certains problèmes sont définitivement et fondamentalement hors d'atteinte du calcul dans un temps raisonnable, et qu'il n'existe pas d'algorithme meilleur que la force brute pour les traiter.

Un des aspect important de ce problème provient du fait qu'il existe une classe de problèmes très importants dits « NP-Complets » dont on ne sait pas s'ils acceptent des solutions données par un algorithme polynomial. Ces problèmes sont importants à double titre : d'une part, ils possèdent souvent une importance intrinsèque (cryptographie à clé publique, problème du voyageur de commerce…), et d'autre part il a été montré que si on trouve une solution à 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.

Parmi ces problèmes NP-Complets, se trouve la cryptanalyse des systèmes de cryptographie à clé publique, utilisée notamment pour la sécurisation des transactions bancaires, et dont la sécurité repose sur l'assertion qu'il n'existe pas d'algorithme polynomial pour casser le système cryptographique. En d'autres termes, la sécurité des transactions bancaires repose sur la supposition que P ≠ NP.

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, ou le calcul de solution optimales en économie (équilibres de Nash), ou dans les processus de fabrication ou de transport.

S'il s'avérait que P=NP, et que cette preuve soit donnée par l'exhibition d'un algorithme polynomial pour un problème NP-Complet, c'est alors toute une série de problèmes très importants qui se trouveraient alors 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.

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 serait alors 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. Trouver la démonstration 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 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 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énaire.

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

S'il était démontré que P ≠ NP, cela signifierait qu'il existe des situations où il est impossible de faire mieux, ou beaucoup mieux, qu'une recherche par force brute pour trouver la solution optimale d'un problème parmi un nombre exponentiel de solutions.

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 serait assurée, mais plus encore : il est démontré que si P ≠ 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.

Une preuve de 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 NP-Complet (sans les rendre polynomiaux pour autant, bien entendu) et pour démontrer plus formellement la sécurité des systèmes cryptographiques.

Toutefois, Stephen Cook fait remarquer que même si P ≠ NP, il reste possible qu'il existe un algorithme résolvant les problèmes NP-Complets dans un temps polynomial, dans un majorité de cas de figure. 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.

Les théoriciens de la complexité algorithmique pensent en majorité que P ≠ NP. 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 que un algorithme polynomial résolvant un problème NP-Complet soit trouvable assez facilement, alors que si on défend 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 à P ≠ NP.

• Plus formellement, un article de Razborov et Rudich de 1993 , qualifié par Scott Aaronson comme l'un des résultats les plus importants concernant le problème P=NP, tend à démontrer que la raison pour laquelle P ≠ NP est si difficile à démontrer, est que probablement P ≠ NP. Cette 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 ≠ NP. Si 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 est de considérer qu'un monde où P=NP est très différent d'un monde où P ≠ NP. Dans un monde où P=NP, des capacités jusqu'ici réservées aux être humains (créativité, recherche..) sont potentiellement accessibles au calcul.

Le fait qu'il soit très difficile de trouver une démonstration à P = NP ou P ≠ NP peut amener à envisager que ce problème est 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 dont la vérité ou la 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 recherche activement une démonstration).

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

R. DeMillo et R. Lipton on démontré en 1979 que dans un certain système formel nommé EF, moins puissant que ZFC, mais suffisament 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. Toutefois, ce résultat vient confirmer que, pour démontrer ce problème, il faudra mettre en oeuvre 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 ≠ 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. De plus, il a été prouvé que le problème Erreur est indécidable avec certains Oracles, dans ZFC, ce qui est considéré comme significatif en faveur de l'indécidabilité du problème.

La classe des problèmes qui peuvent être résolus efficacement par des calculateurs quantiques est appellée BQP, pour "Bounded error, Quantum, Polynomial time". Les calculateurs quantiques exécutent uniquement des algorithmes probabilistes, et constitue la contrepartie de la classe de complexité BBP pour les ordinateurs classiques. 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, 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. Notamment, il existe un algorithme quantique qui s'applique aux problèmes NP-Complet : l'algorithme de Grover, mais qui n'est pas polynomial (bien que plus rapide que les algorithmes classiques), et il existe de forts indices selon lequels on ne pourra pas aller plus loin en matière d'algorithme quantique.

Enfin, il convient de remarquer que les calculateurs quantiques sont un type particulier de machines de Turing. La thèse de Church s'applique donc a priori aux calculateurs quantique, 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.

• Lance Fortnow The Status of the P versus NP Problem Communications of the ACM Vol. 52, Issue 9 (Septembre 2009) :

• Stephen Cook The P versus NP problem. Official description.:

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

• Scott Aaronson Is P Versus NP Formally Independent? :