Problem Detail: 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.
Asked By : aelguindy
Answered By : Boris Trayvas
No, because $mathsf{P}$ is closed to complement this cant be, and we even know that $mathsf{P}=mathsf{NP} implies mathsf{NP}=mathsf{cotext{-}NP}$. Let us assume that $mathsf{P}=mathsf{NP}$, and let $L in mathsf{cotext{-}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{cotext{-}NP}$ and thus $mathsf{P}=mathsf{cotext{-}NP}$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/2341 Ask a Question Download Related Notes/Documents
