Co-NP

Nella teoria della complessità computazionale, $coNP$ è la classe di problemi complementari a quelli della classe $NP$. In maniera più formale si ha che se $S$ è un problema su un alfabeto $A$ allora esso è un problema della classe $coNP$ se e solo se $A^{*}\backslash S=S^{c}$ è un problema di classe $NP$.

Per quanto riguarda l'uguaglianza $coNP=NP$ non ci si può esprimere.

Infatti per vedere se un certo input $w\in A^{*}$ sia tale da essere di $S$ o di non esserlo si dovrebbe attendere che tutte le possibili computazioni della macchina di Turing non deterministica che accetta $S^{c}$ facciano il loro corso; ossia per avere la certezza che $w\in S$ nessuna computazione si dovrebbe arrestare mentre se $w\not \in S$ allora almeno una di tali computazioni si dovrebbe arrestare. Per far ciò non si impiega però un tempo polinomiale.

Ecco perché non si può dire nulla a proposito dell'uguaglianza $coNP$ ed $NP$.