Classe co-NP

Définition

La classe co-NP contient les complémentaires des problèmes de Classe NP.

$$co\text{-}NP=\{Q\mid \bar{Q}\in NP\}$$

Autrement dit, si un problème appartient à NP, sa négation logique (le problème inverse) appartient à co-NP.

Exemple

• Le complément de SAT (formule non satisfiable) : UNSAT ∈ co-NP
• Le problème du tri : vérifier qu’une liste est non triée ∈ co-P = P

Relations avec les autres classes

• $P\subseteq NP\cap co\text{-}NP$
• Si $NP=co\text{-}NP$, alors $P=NP$ (théorème du CM7)
• Mais on pense généralement que $NP\ne co\text{-}NP$

Intuition

• Dans NP, on peut prouver qu’une instance est vraie (via un certificat).
• Dans co-NP, on peut prouver qu’une instance est fausse (via un certificat).