principleModerate
Can exactly one of NP and co-NP be equal to P?
Viewed 0 times
canequaloneandexactly
Problem
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.
Solution
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}$.
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}$.
Context
StackExchange Computer Science Q#2341, answer score: 14
Revisions (0)
No revisions yet.