Co-NP

En informatique théorique, co-NP (ou coNP) est une classe de complexité, c'est-à-dire un ensemble de problèmes de décision 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

On donne deux définitions équivalentes.

À partir de NP

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

On peut définir la classe coNP en utilisant des certificats^[1]. Sur un alphabet ${\displaystyle \Sigma }$, un langage ${\displaystyle L}$ est dans co-NP, s'il existe un polynôme ${\displaystyle P}$ et une machine de Turing en temps polynomial ${\displaystyle M}$, tels que pour un mot ${\displaystyle x}$, on a équivalence entre ${\displaystyle x\in L}$ et le fait que pour tout certificat ${\displaystyle c\in \Sigma ^{P(|x|)}}$, la machine ${\displaystyle M}$ accepte l'entrée ${\displaystyle (x,c)}$.

Problèmes co-NP-difficiles

Comme pour la classe NP, on définit la notion de problèmes co-NP-difficile. Un problème est co-NP-difficile si tout problème co-NP s'y réduit en temps polynomial. Un problème est co-NP-complet s'il est dans co-NP et il est co-NP-difficile.

Exemples

De tout problème dans NP, on peut construire un problème « dual » dans co-NP.

Problème dans NP	Problème complémentaire dans coNP
le problème SAT : étant donné une formule booléenne, existe-t-il une assignation de ses variables qui la rend vraie ?	étant donné une formule booléenne, est-elle fausse pour toute assignation de ses variables[2] ? (même si on considère plutôt le problème de la validité qui est inter-réductible au problème précédent : étant donné une formule booléenne, est-elle vraie pour toutes les assignations de ses variables[2] ?)
le problème du chemin hamiltonien : étant donné un graphe G, existe-t-il un chemin hamiltonien ?	le problème de la non-existence d'un chemin hamiltonien : étant donné un graphe G de n nœuds et m arcs, est-il vrai qu'aucune combinaison de n arcs parmi m ne constitue un chemin hamiltonien?
le problème de la clique : étant donné un graphe G et un entier k, existe-t-il une clique de taille k dans G ?	le problème de la non-clique : étant donné un graphe G et un entier k, est-il vrai que G ne possède pas de clique de taille k ?

Liens avec les autres classes

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

On sait que ${\displaystyle P\subseteq NP\cap co{-}NP}$, mais l'égalité est une question ouverte. Le problème du test de primalité est connu pour être dans NP et co-NP, mais on pensait généralement qu'il n'était pas dans P ; jusqu'à ce qu'en 2002 on démontre qu'il est dans P (Théorème AKS).

Dans la hiérarchie polynomiale, co-NP correspond au premier étage existentiel : co-NP = ${\displaystyle \Pi _{1}^{p}}$.

Co-NP-complet

En théorie de la complexité, un problème est dit co-NP-complet s'il est co-NP et si tout problème co-NP est réductible en temps polynomial à lui. Autrement dit, c'est la classe des problèmes complets correspondant à co-NP. Tout problème co-NP-complet est le complémentaire d'un problème NP-complet.

Bibliographie

• (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

• (fr) Maths Adulte La Rochelle université : Le résultat qui sème le doute
• (en) La classe co-NP sur le Complexity Zoo

Notes et références

• Cet article est partiellement ou en totalité issu de l'article intitulé « Co-NP-complet » (voir la liste des auteurs).

1. Sylvain Perifel, Complexité algorithmique, Ellipses, 2014, 432 p. (ISBN 9782729886929, lire en ligne), chap. 2.2 (« Temps non-déterministe ») Proposition 2-BA, p. 62.
2. (en) Papadimitriou, Computational Complexity, Addison Wesley, 1994, p. 220.
3. (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 learned? ».

• Portail de l'informatique théorique