Co-NP

Da Wikipedia, l'enciclopedia libera.

La classe coNP[modifica | modifica wikitesto]

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.