Visualizza wikitesto di Co-NP

{{F|teorie dell'informatica|arg2=matematica|dicembre 2014}}
Nella [[teoria della complessità computazionale]], <math>coNP</math> è la [[Classe di complessità|classe]] di problemi [[Complemento (complessità)|complementari]] a quelli della classe <math>NP</math>. In maniera più formale si ha che se <math>S</math> è un problema su un alfabeto <math>A</math> allora esso è un problema della classe <math>coNP</math> se e solo se <math>A^* \backslash S = S^c</math> è un problema di classe <math>NP</math>.

Per quanto riguarda l'uguaglianza <math>coNP = NP</math> non ci si può esprimere.

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

{{Classi di complessità}}
{{Portale|informatica|matematica}}

[[Categoria:Classi di complessità]]