8
$\begingroup$

Maybe I am missing something obvious, but can it be that P = co-NP $\subsetneq$ NP or vice versa? My feeling is that there must be some theorem that rules out this possibility.

$\endgroup$
14
$\begingroup$

No, because $\mathsf{P}$ is closed to complement this cant be, and we even know that $\mathsf{P}=\mathsf{NP} \implies \mathsf{NP}=\mathsf{co\text{-}NP}$.

Let us assume that $\mathsf{P}=\mathsf{NP}$, and let $L \in \mathsf{co\text{-}NP}$, thus $L^c \in \mathsf{NP}$. We assumed $\mathsf{P}=\mathsf{NP}$, and therefore there exists a TM $M$ s.t. $L(M)=L^c$. If we take the "complement" of $M$, that is a machine $M'$ which is identical to $M$ except its accept and reject states are reversed, we get that $L(M')=(L^c)^c=L$, and thus $L$ is in $\mathsf{NP}$.

This shows that, under the assumption that $\mathsf{P}=\mathsf{NP}$, we get $(\mathsf{P}=)\mathsf{NP}=\mathsf{co\text{-}NP}$ and thus $\mathsf{P}=\mathsf{co\text{-}NP}$.

$\endgroup$
9
$\begingroup$

$\mathsf{P}$ is closed under complement (i.e. $\mathsf{P}=\mathsf{co\text{-}P}$ ¹); so if $\mathsf{P}=\mathsf{co\text{-}NP}$ (or $\mathsf{P}=\mathsf{NP}$) then $\mathsf{co\text{-}NP} = \mathsf{NP}$


  1. Given a language $L \in \mathsf{P}$, we can construct a deterministic TM' that decides $\overline L$ in polynomial time simply by taking the TM that decides $L$ and ...
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.