Indietro

ⓘ Co-NP




Co-NP
                                     

ⓘ Co-NP

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

Per quanto riguarda luguaglianza c o N P = N P {\displaystyle coNP=NP} non ci si può esprimere.

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