Co-NP

La classe coNP

La classe $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$.