[Solved]: If NP is not a proper subset of coNP, why does NP not equal coNP?

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?

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.

$P\subseteq 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