NP-complet

Le terme NP-complet renvoie à la théorie de la complexité. L'ouvrage de référence sur le sujet est celui de Garey et Johnson Computers and intractability. A guide to the theory of NP-completness publié en 1979. Un problème de décision consiste à déterminer pour une instance quelconque fournie en entrée s'il existe une solution satisfaisant des contraintes décrivant une propriété d'intérêt, par exemple, s'il existe une façon de compléter une grille donnée de sudoku vérifiant les contraintes imposées par ce jeu. Un problème de décision est NP-complet si :

• il est dans la classe de complexité NP (Non déterministe polynomial), c'est-à-dire : on peut vérifier qu'une solution potentielle de taille n satisfait les contraintes du problème par un algorithme dont le temps de calcul est majoré par une fonction polynome de n,
• et il est NP-difficile, c'est-à-dire : si on trouve un algorithme déterministe polynomial pour le résoudre, alors on saura résoudre en temps polynomial n'importe quel problème de NP.

Le sous-ensemble des problèmes NP-complets constitue le noyau dur de la classe de complexité NP. Trouver un algorithme efficace pour résoudre l'un d'entre eux permettrait de prouver que P=NP (et de devenir millionnaire). Si on admet que P est différent de NP, alors il n'existe pas de résolution informatique efficace des problèmes NP-complets que l'on rencontre dans de nombreux problèmes réels, sauf si on les restreint à des cas particuliers plus simples. La résolution des problèmes NP-complets se heurte à l'explosion combinatoire du nombre de solutions potentielles à vérifier, qui peut nécessiter un temps de calcul exponentiel. C'est toute la nuance entre « trouver une solution » et « vérifier une solution ».