5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ To whoever down-voted, what is wrong with the question, please? $\endgroup$ – Caleb Owusu-Yianoma Oct 26 '16 at 19:18
  • 8
    $\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$ – Alexey Romanov Oct 26 '16 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$ – Caleb Owusu-Yianoma Oct 28 '16 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$ – Caleb Owusu-Yianoma Oct 28 '16 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$ – Caleb Owusu-Yianoma Oct 28 '16 at 17:37
7
$\begingroup$

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

$\endgroup$
  • $\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$ – Caleb Owusu-Yianoma Oct 28 '16 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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