Ouvrir le menu principal

NP (complexité)

classe de complexité des problèmes algorithmique; problèmes pouvant être résolu en temps polynomial par une machine de Turing non-déterministe
Page d'aide sur l'homonymie 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.

Sommaire

DéfinitionsModifier

Définition par machine non déterministeModifier

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 certificatModifier

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étudeModifier

Article détaillé : problème NP-complet.

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 le problème du voyageur de commerce.

Relations avec les autres classesModifier

 
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érisationsModifier

BibliographieModifier

Lien externeModifier

Notes et référencesModifier

  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.