Pour les articles homonymes, voir NP.

La classe NP est une classe très importante de la théorie de la complexité. L'abréviation NP signifie « non déterministe polynomial » (« nondeterministic polynomial time »). Un problème de décision est dans NP s'il est décidé par une machine de Turing non déterministe en temps polynomial par rapport à la taille de l'entrée. Intuitivement, cela revient à dire qu'on peut vérifier « rapidement » (complexité polynomiale) si une solution candidate est bien solution. Par exemple, considérons le problème de décision du voyageur de commerce qui, étant donné un entier k et un ensemble de villes séparées par des distances, détermine s'il existe un circuit de longueur inférieure à k qui passe une et une seule fois par toutes les villes. On vérifie « rapidement » qu'une solution candidate, ici un chemin quelconque, est bien solution, c'est-à-dire que c'est bien un circuit de longueur inférieur à k et qu'il passe bien une et seule fois par toutes les villes.

L'un des grands problèmes ouverts de l'informatique théorique est le Problème P ≟ NP.

On appelle NTIME(t(n)) la classe des problèmes de décision qui peuvent être résolus en temps de l'ordre de grandeur de t(n) sur une machine de Turing non déterministe (où n est la taille de l'entrée).

Alors NP = ${\displaystyle \scriptstyle \cup _{c>1}}$NTIME(${\displaystyle \scriptstyle n^{c}}$).

Sur un alphabet ${\displaystyle \Sigma }$, un langage ${\displaystyle L}$ est dans NP s'il existe un polynôme ${\displaystyle P}$ et une machine de Turing déterministe en temps polynomial ${\displaystyle M}$, tels que pour un mot ${\displaystyle x}$ de taille ${\displaystyle n}$ : ${\displaystyle x\in L\Leftrightarrow \exists u\in \Sigma ^{P(n)},M(x,u)=1}$ (où ${\displaystyle M(x,u)=1}$ signifie que la machine accepte sur l'entrée (x,u))^[1].

Autrement dit, il existe un « indice », appelé certificat, qui permet de prouver rapidement que le mot est dans le langage.

Les problèmes NP-complets sont les problèmes de NP qui sont aussi NP-difficiles. Ce sont les problèmes les plus difficiles de la classe dans le sens où l'on peut ramener tout problème de NP à ces problèmes par certaines réductions, en particulier des réductions polynomiales.

De nombreux problèmes ont été identifiés comme NP-complets^[2], dont le problème SAT ou encore Circuit Hamiltonien.

On a l'inclusion P ${\displaystyle \scriptstyle \subseteq }$ NP mais l'une des grandes questions ouvertes de l'informatique théorique est le problème de savoir si oui ou non P = NP.

Dans les classes usuelles, on peut aussi citer une surclasse : NP${\displaystyle \subseteq }$ PSPACE.

NP permet en outre de définir co-NP, la classe complémentaire. Ces deux classes forment le premier niveau de la hiérarchie polynomiale. Le théorème de Karp-Lipton affirme que si NP admet des circuits de tailles polynomiales, alors la hiérarchie polynomiale s'effondre au niveau 2.

• L'un des grands résultats de complexité descriptive est le théorème de Fagin, qui montre l'équivalence entre les problèmes de NP et ceux exprimables dans la logique ESO.
• Le théorème PCP permet de décrire la classe NP dans le contexte d'un système de preuve interactive, plus précisément PCP[O(log n), O (1)] = NP.

• (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, 2009 (ISBN 0-521-42426-7)

• (en) La classe NP sur le Complexity Zoo

• Portail de l'informatique théorique