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é. Un problème de décision est dans NP s'il peut être décidé sur une machine de Turing non-déterministe en temps polynomial par rapport à la taille de l'entrée.

L'un des grands problèmes 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 = \scriptstyle \cup_{c>1}NTIME(\scriptstyle n^c).

Définition par certificat[modifier | modifier le code]

Sur un alphabet \Sigma, un langage L est dans NP s'il existe un polynôme P et une machine de Turing 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))[1].

Autrement dit il existe un « indice » (un 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 \scriptstyle \subseteq NP mais l'une des grandes questions ouvertes de l'informatique théorique est le problème de savoir si P=NP ou pas.

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.

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,‎ 2009 (ISBN 0-521-42426-7) chap 2.1, The class NP
  2. Voir Liste de problèmes NP-complets.