NP (complexité)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
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érieur à 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 | modifier le code]

Définition par machine non déterministe[modifier | modifier le code]

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 | modifier le code]

Sur un alphabet , un langage est dans NP s'il existe un polynôme et une machine de Turing 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 | modifier le code]

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

Relations avec les autres classes[modifier | modifier le code]

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

Autres caractérisations[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

Lien externe[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  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.