Co-NP

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

co-NP (ou coNP) est une classe de complexité, c'est-à-dire un ensemble de problèmes au sens de la théorie de la complexité. C'est la classe complémentaire (au sens de la complexité) de la classe NP.

Définitions[modifier | modifier le code]

À partir de NP[modifier | modifier le code]

co-NP est l'ensemble des langages qui ont pour complémentaire (au sens des langages) un langage de NP.

Une autre façon de voir est que co-NP est l'ensemble des langages pour lesquels une preuve vérifiable en temps polynomial peut prouver la non-appartenance du mot au langage (des contre-exemples).

Par certificat[modifier | modifier le code]

On peut définir la classe coNP en utilisant des certificat[1]. Sur un alphabet \Sigma, un langage L est dans co-NP, si 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 \forall u \in \Sigma^{P(n)},M(x,u)=1.

Notion de problème co-NP-complet[modifier | modifier le code]

Comme pour NP, on peut définir des problèmes complets au sens des réductions polynomiales pour la classe co-NP, ce sont les problèmes co-NP-complet.

Un exemple de tel problème est le problème de la tautologie : étant donné une formule booléenne, est-elle vraie pour toutes les assignations de ses variables?

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

La question co-NP=NP est une question ouverte mais il est conjecturé que ces classes sont différentes[2]. Si P=NP alors NP=co-NP mais la réciproque n'est pas connue.

On sait que P\subseteq NP\cap co-NP, mais l'égalité est une question ouverte. Un problème connu à la fois dans NP et dans co-NP est la décomposition en produit de facteurs premiers (Integer factorization en anglais).

Dans la hiérarchie polynomiale, co-NP correspond au premier étage existentiel : co-NP=\Pi_1^p.

Bibliographie[modifier | modifier le code]

(en) Sanjeev Arora et Boaz Barak, Computational Complexity : A modern Approach, Cambridge University Press,‎ 2009 (ISBN 0-521-42426-7), chap. 2.6 (« co-NP, EXP and NEXP »)

Liens externes[modifier | modifier le code]

(en) La classe co-NP sur le Complexity Zoo

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

  1. Sylvain Perifel, Complexité algorithmique, Ellipses,‎ 2014 (ISBN 9782729886929, lire en ligne), chap. 2.2 (« Temps non-déterministe ») Proposition 2-BA, p.62.
  2. (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A modern Approach, Cambridge University Press,‎ 2009 (ISBN 0-521-42426-7), chap. 2.6 (« co-NP, EXP and NEXP ») "What have we learn ?"