title: Co-NP
text: # 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. Sur un alphabet $\Sigma$, un langage $L$ est dans co-NP, s'il existe un polynôme $P$ et une machine de Turing en temps polynomial $M$, tels que pour un mot $x$, on a équivalence entre $x\in L$ et le fait que pour tout certificat $c\in \Sigma ^{P(|x|)}$, la machine $M$ accepte l'entrée $(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 ? (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 ?) |
  | 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. 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. 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 = $\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.
  
  