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.