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.
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
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}$.
$\begingroup$
$\endgroup$
$\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}$
- 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 ...
