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