Co-NP

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

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

Infatti per vedere se un certo input ${\displaystyle w\in A^{*}}$ sia tale da essere di ${\displaystyle S}$ o di non esserlo si dovrebbe attendere che tutte le possibili computazioni della macchina di Turing non deterministica che accetta ${\displaystyle S^{c}}$ facciano il loro corso; ossia per avere la certezza che ${\displaystyle w\in S}$ nessuna computazione si dovrebbe arrestare mentre se ${\displaystyle 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 ${\displaystyle coNP}$ ed ${\displaystyle NP}$.

Portale Informatica

Portale Matematica