Voir la source de Co-NP

En [[informatique théorique]], '''co-NP''' (ou '''coNP''') est une [[classe de complexité]], c'est-à-dire un ensemble de [[Problème de décision|problèmes de décision]] au sens de la [[théorie de la complexité (informatique théorique)|théorie de la complexité]]. C'est la classe [[complémentaire (complexité)|complémentaire (au sens de la complexité)]] de la classe '''[[NP (complexité)|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 (complexité)|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 [[certificat (complexité)|certificats]]<ref>{{Complexité algorithmique (Perifel)|numéro chapitre=2.2|titre chapitre=Temps non-déterministe}} Proposition 2-BA, {{p.|62}}.</ref>.
Sur un alphabet <math>\Sigma</math>, un langage <math>L </math> est dans co-NP, s'il existe un [[polynôme]] <math>P</math> et une [[machine de Turing]] en temps polynomial <math>M</math>, tels que pour un mot <math>x</math>, on a équivalence entre  <math>x\in L</math> et le fait que ''pour tout'' certificat <math>c \in \Sigma^{P(|x|)}</math>, la machine <math>M</math> accepte l'entrée <math>(x, c)</math>.

== Problèmes co-NP-difficiles ==
Comme pour la classe NP, on définit la notion de problème '''co-NP-difficile'''. Un problème est co-NP-difficile si tout problème co-NP s'y [[Réduction polynomiale|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.
{| class="wikitable"
!Problème dans NP
!Problème complémentaire dans coNP
|-
|le [[problème SAT]] : étant donné une formule booléenne, {{Souligner|existe-t-il}} une assignation de ses variables qui la rend vraie ?
|étant donné une formule booléenne, est-elle fausse {{Souligner|pour toute}} assignation de ses variables<ref name=":0">{{Ouvrage|langue = en|auteur1 = Papadimitriou|titre = Computational Complexity|éditeur = Addison Wesley|année = 1994|isbn = |lire en ligne = |passage = p. 220}}.</ref> ? (même si on considère plutôt le problème de la [[Validité (logique)|validité]] qui est inter-[[Réduction polynomiale|réductible]] au problème précédent : étant donné une formule booléenne, est-elle vraie {{Souligner|pour toutes}} les assignations de ses variables<ref name=":0" /> ?)
|-
|le problème du [[chemin hamiltonien]] : étant donné un graphe ''G'', {{Souligner|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 (théorie des graphes)|clique]] : étant donné un graphe ''G'' et un entier ''k'', {{Souligner|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'' {{Souligner|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<ref>{{Computational Complexity (Arora et Barak)|numéro chapitre=2.6|titre chapitre = co-NP, EXP and NEXP}} « {{Langue|en|What have we learned?}} ».
</ref>. Si [[Problème P = NP|P = NP]], alors NP = co-NP mais la réciproque n'est pas connue.

On sait que <math>P\subseteq NP\cap co{-}NP</math>, 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 ([[Test de primalité AKS|Théorème AKS]]).

Dans la [[hiérarchie polynomiale]], co-NP correspond au premier étage universel : co-NP = <math>\Pi_1^p</math>.

== Co-NP-complet ==
En [[théorie de la complexité des algorithmes|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éduction polynomiale|réductible en temps polynomial]] à lui. Autrement dit, c'est la classe des problèmes [[complet (complexité)|complets]] correspondant à ''co-NP''. Tout problème co-NP-complet est le complémentaire d'un problème NP-complet.

== Bibliographie ==
* {{Computational Complexity (Arora et Barak)|numéro chapitre=2.6|titre chapitre = co-NP, EXP and NEXP}}

== Liens externes ==
* {{fr}} [https://www.youtube.com/watch?v=aPYmHroE0Nw Maths Adulte La Rochelle université : Le résultat qui sème le doute]
* {{complexity Zoo|fin=C#conp|nom=co-NP}}

== Notes et références ==
{{Crédit d'auteurs|interne|Co-NP-complet}}
{{Références}}

{{Palette|Théorie de la complexité}}

{{Portail|informatique théorique}}

[[Catégorie:Classe de complexité]]