NP (complexité)

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.

Définitions

Définition par machine non déterministe

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 = $\scriptstyle \cup _{c>1}$NTIME($\scriptstyle n^{c}$).

Définition par certificat

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

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

NP-complétude

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, dont le problème SAT ou encore Circuit Hamiltonien.

Relations avec les autres classes

Représentations des inclusions des classes usuelles.

On a l'inclusion P $\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$\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.

Autres caractérisations

• 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.

Bibliographie

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

Lien externe

• (en) La classe NP sur le Complexity Zoo