Problem Detail: I am studying some lecture notes on the complexity of algorithms.
The notes give a proof that NP is not a proper subset of coNP.
However, they still assert that NP is a subset of coNP (which I agree with).
So, in this case, why does it not follow that NP is equal to coNP?
The notes give a proof that NP is not a proper subset of coNP.
However, they still assert that NP is a subset of coNP (which I agree with).
So, in this case, why does it not follow that NP is equal to coNP?
Asked By : CKKOY
Answered By : jmite
${2,3}$ is not a proper subset of ${3,4}$, yet the two clearly are not equal. Comparing sets is not like comparing numbers: two sets might not be comparable. Additionally, NP is not a subset of coNP, or at least, it is not known that this is the case. You are either misreading the textbook, or your textbook is wrong, since proving that $NP subseteq coNP$ would be a massive result. $Psubseteq coNP$, perhaps that is what you actually read?
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/65159 Ask a Question Download Related Notes/Documents
