Co-NP

Da Wikipedia, l'enciclopedia libera.

Nella teoria della complessità computazionale, è la classe di problemi complementari a quelli della classe . In maniera più formale si ha che se è un problema su un alfabeto allora esso è un problema della classe se e solo se è un problema di classe .

Per quanto riguarda l'uguaglianza non ci si può esprimere.

Infatti per vedere se un certo input sia tale da essere di o di non esserlo si dovrebbe attendere che tutte le possibili computazioni della macchina di Turing non deterministica che accetta facciano il loro corso; ossia per avere la certezza che nessuna computazione si dovrebbe arrestare mentre se 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 ed .