Problème P = NP - Définition
La liste des auteurs de cet article est disponible ici.
Introduction
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) = N2). 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.
Implications de P ≠ NP
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.
