Co-NP

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

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

On donne deux définitions équivalentes.

À 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 certificats[1]. Sur un alphabet , un langage est dans co-NP, s'il existe un polynôme et une machine de Turing en temps polynomial , tels que pour un mot , on a équivalence entre et le fait que pour tout certificat , la machine accepte l'entrée .

Problèmes co-NP-difficiles[modifier | modifier le code]

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

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, est-il vrai qu'il n'a pas de chemin hamiltonien ?[2]
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[modifier | modifier le code]

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 , mais l'égalité est une question ouverte. Le problème de la décomposition en produit de facteurs premiers est connu pour être dans NP et co-NP, mais on pense généralement qu'il n'est pas dans P.

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

Co-NP-complet[modifier | modifier le code]

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

(en) Sanjeev Arora et Boaz Barak, Computational Complexity : A modern Approach, Cambridge University Press, (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, , 432 p. (ISBN 9782729886929, lire en ligne), chap. 2.2 (« Temps non-déterministe ») Proposition 2-BA, p. 62.
  2. a, b et c Papadimitriou, Computational Complexity, Addison Wesley, , p. 220
  3. (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A modern Approach, Cambridge University Press, (ISBN 0-521-42426-7), chap. 2.6 (« co-NP, EXP and NEXP ») "What have we learn ?"