Co-NP

Template:F 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^{*}\mathrm{\setminus }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\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$.