# If NP is not a proper subset of coNP, why does NP not equal coNP?

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?

• To whoever down-voted, what is wrong with the question, please? – Caleb Owusu-Yianoma Oct 26 '16 at 19:18
• There is no known proof that NP is a subset of coNP (because if there were, you'd indeed immediately conclude NP=coNP). Thus, either 1) you misunderstood the notes; 2) the notes are wrong; or 3) the author accidentally solved NP=coNP and didn't notice. 3) seems by far the least likely. – Alexey Romanov Oct 26 '16 at 19:49
• I couldn't help but laugh! :D I think the answer is a variation on 2) - the notes are not very clearly written, and the reader can easily think (as I did) that it is a fact that NP is a subset of coNP. I think the author actually makes an implicit assumption (in a proof by contradiction) that NP is a subset of coNP, but does not clarify. – Caleb Owusu-Yianoma Oct 28 '16 at 17:13
• On that note, why exactly isn't NP a subset of coNP? If a decision problem $X$ is in NP, why can't we simply say that its complement, $\bar{X}$, is in NP because the complement of a decision problem is the decision problem resulting from reversing the yes and no answers (we could take the Turing Machine that computes $X$ and reverse its inputs and outputs, no?)? (I took the definition of 'complement of a decision problem' from: en.wikipedia.org/wiki/Complement_(complexity)) – Caleb Owusu-Yianoma Oct 28 '16 at 17:32
• Hmm...my comment above may be seen as redundant, since my lecture notes prove that NP is not a proper subset of coNP (and, clearly, if it is not a proper subset, the only options that remain are that it is either equal to coNP [which has not been proved ;)] OR it is not a subset of coNP at all). However, I have made the above comment because I'm trying to play devil's advocate. Why couldn't one argue that NP is equal to coNP using my reasoning in the above comment? – Caleb Owusu-Yianoma Oct 28 '16 at 17:37

$\{2,3\}$ is not a proper subset of $\{3,4\}$, yet the two clearly are not equal.
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?