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?

  • 9
    $\begingroup$ 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. $\endgroup$ Oct 26, 2016 at 19:49
  • $\begingroup$ 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. $\endgroup$ Oct 28, 2016 at 17:13
  • $\begingroup$ 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)) $\endgroup$ Oct 28, 2016 at 17:32
  • $\begingroup$ 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? $\endgroup$ Oct 28, 2016 at 17:37
  • $\begingroup$ Because the definition of NP is not symmetric w.r.t. yes/no answers. $\endgroup$ Oct 28, 2016 at 19:07

2 Answers 2


$\{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?

  • $\begingroup$ Yes, I am aware that comparing sets is not like comparing numbers. As I mentioned in a comment above, I think the author purposely makes an implicit assumption that NP is a coNP, in order to carry out a proof by contradiction of another result. It's just that the implicit assumption can be easily misunderstood and viewed as a fact. $\endgroup$ Oct 28, 2016 at 17:15

NP is not the subset of co-NP unless we assume A be an NP-Complete problem and A∈ co-NP (which is not possible) then we can say all NP problems are a subset of co-NP problems since we can reduce all NP problems to problem A which is NP-complete it follows that for every problem in NP, we can construct a non-deterministic Turing machine that decides its complement in polynomial time; i.e., NP ⊆ co-NP. From this, it follows that the set of complements of the problems in NP is a subset of the set of complements of the problems in co-NP.

More information can be found Here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.