NP (complexité)

classe de complexité des problèmes algorithmiques ; problèmes pouvant être résolus en temps polynomial par une machine de Turing non-déterministe
(Redirigé depuis Classe 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.

Définitions

modifier

Définition par machine non déterministe

modifier

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 =  NTIME( ).

Définition par certificat

modifier

Sur un alphabet  , un langage   est dans NP s'il existe un polynôme   et une machine de Turing déterministe en temps polynomial  , tels que pour un mot   de taille   :   (où   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.

NP-complétude

modifier

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.

Relations avec les autres classes

modifier
 
Représentations des inclusions des classes usuelles.

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

modifier

Bibliographie

modifier

Lien externe

modifier

Notes et références

modifier
  1. (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, (ISBN 0-521-42426-7) chap 2.1, « The class NP ».
  2. Voir Liste de problèmes NP-complets.