Problème P = NP - Définition
La liste des auteurs de cet article est disponible ici.
Importance et implications de P=NP
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 CN 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 CN 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é.
