Résumé :
En 1971, Cook a demontré que tout calcul sur une machine de Turing non déterministe se réduit à un problème de satisfaction d'une formule booléenne, résultat aussi démontré par Levin en Russie.
La classe P contient les problèmes pour lesquels il existe une solution efficace (en temps polynomial), la classe NP contient les problèmes dont on sait vérifier une solution de façon efficace. P est inclus dans NP, la question est majeure, vieille de trente ans, est de savoir si cette inclusion est stricte.
Approches
Un problème est dit NP-complet si tout problème de NP peut lui être réduit ; intuitivement les problèmes NP-complets sont les problèmes NP les plus difficiles.
Parmi les problèmes NP-complets on compte celui de la satisfaction des formules booléennes, celui de décider si un graphe est Hamiltonien, celui de déterminer si la clique maximale d'un graphe est de taille k ou non.
Une approche a consisté à tenter de prouver qu'un problème NP-complet est soluble en temps polynomial. Tentative infructueuse, bien que la littérature officieuse propose de nombreuses preuves de ce genre.
- La diagonalisation :
Via cette technique on a cherché à exhiber un problème de NP qui ne soit pas dans P, cependant en 1975 il a été prouvé que pour un oracle A, NP=P. Ceci signifie qu'une preuve de non(P=NP) doit être indépendante de l'oracle, et que donc la méthode par diagonalisation a peu de chance d'aboutir.
- La conjecture d'isomorphisme :
Malgré leur variété,
une conjecture affirme que tous les problèmes NP-complets sont de
fait identiques à une permutation près de leurs éléments.
Cette conjecture, dite conjecture d'isomorphisme, a été formulée
par Hartmanis et Berman.
Prouver cette conjecture impliquerait
que non(P=NP).
Notons que tous les problèmes NP complets connus sont denses (le nombre d'instance est exponentiel en la taille de l'instance). Il s'en suit que si un problème NP-complet n'est pas dense, alors la conjecture d'isomorphisme est fausse, et de plus un résultat important affirme que dans ce cas P=NP.
Interprétations
- La présentation des preuves :
Un article de Hartmanis et Yesha
argumente en faveur de P=NP, et P=P-Space ; il disserte aussi sur la comparaison
entre la créativité et la puissance de calcul brute que cette
question implique.
La différence entre NP et
P-Space est celle existant entre (un tableau + une craie) et (un tableau
+ une craie + un effaceur).
- La vérification des preuves (le théorème PCP)
La solution d'un problème dans NP est une preuve déterministe ; la preuve du fait qu'une formule booléenne soit satisfaisable étant donnée une affectation des variables. Ce type de preuve est long (n bits).
On a donc cherché à
définir des preuves approchées interactives :
Un vérificateur agit en
fonction des bits de la formule à vérifier et d'un certain
nombre de bits aléatoires. À la fin du processus le vérificateur
décide si oui ou non la formule est satisfaisable.
Il a été prouvé
que :
Il existe un vérificateur
fonctionnant en temps polynomial, accédant à un nombre constant
de bits de la formule et utilisant log(n) bits aléatoires tel que
si la formule est satisfaisable le vérificateur répond toujours
oui ; si la formule n'est pas satisfaisable le vérificateur répond
non avec probabilité inférieure à 1/2.
Applications
- Les deux mondes :
Si P=NP, l'impact serait énorme puisque des milliers de problèmes combinatoires se trouveraient être soluble en temps polynomial. Un tel résultat aurait des conséquences pratiques sans nombre (logistique, ordonnancement, routage des véhicules, localisation de ressources).
Si non(P=NP), le monde serait bien
moins efficace.
Par ailleurs ce résultat
impliquerait que de nombreux problèmes d'optimisation ne peuvent
être résolu même de manière approchée
en temps raisonnable. Une conséquence et non des moindres serait
aussi de prouver l'inviolabilité de certaines méthodes de
cryptage.