4
$\begingroup$
  • What do we need about the intersection of $NP$ and $co-NP$ apart from the fact that $P$ is a subset of it?

(beyond what these answers here say, What do we know about NP ∩ co-NP and its relation to NPI?, if $L\in NP\cap Co-NP$ is NP-Hard, then $NP=Co-NP$)

  • Is there an example of a decision question which is known to be $co-NP /\ NP$ or $NP /\ co-NP$? (and great consequences of such a thing existing in the even that P not the same as NP)

  • Do we know anything about how BPP, RP, co-RP or ZPP intersect NP or co-NP? (apart from the fact that $(P \subset (ZPP = RP \cap co-RP)) \subset BPP$ and hence whatever intersection with NP and co-NP follows just from this)

$\endgroup$
  • 2
    $\begingroup$ We can't separate NP from coNP since, as you mention, this would imply that P$\neq$NP. As far as I know, we also cannot conclude that NP$\neq$coNP from P$\neq$NP. $\endgroup$ – Yuval Filmus Apr 16 '15 at 23:44
  • $\begingroup$ Thanks! (1) So no decision questions of the kind I asked for in the second bullet point are known? (2) Any thoughts about the last bullet point? $\endgroup$ – user6818 Apr 17 '15 at 21:57
  • $\begingroup$ The Wikipedia pages on BPP and RP mentions that their connection to NP is unknown, and the same probably holds for ZPP as well. You can also check the complexity zoo. $\endgroup$ – Yuval Filmus Apr 17 '15 at 22:14
  • $\begingroup$ 1. What research have you done? There's lots known. 2. One question per question, please. "What do we know about $NP \cap coNP$?" is too broad a question for this site (see our help center). Asking several different questions is not suitable for this site -- we expect one question per question. Please identify one specific, answerable technical question, and ask that in this question -- you can post the other question separately in a separate question. But don't mash up 3 different questions together into the same post; that doesn't work so well with this site's format. $\endgroup$ – D.W. Apr 17 '15 at 22:22
  • 1
    $\begingroup$ Isn't it better to club together related questions? I would think that the cohesion of ideas would be lost if I split it up. Thanks for the help BTW! $\endgroup$ – user6818 Apr 17 '15 at 22:31
7
$\begingroup$

There is no decision problem that is (unconditionally) known to be in $coNP \setminus NP$. If we had a decision problem that we could prove is in $coNP$ and could prove is not in $NP$, then we would have proven that $NP \ne coNP$, from which it follows that $P \ne NP$. In other words, if we knew of such a problem, a proof that is in $coNP \setminus NP$ would provide a proof that $P \ne NP$. But of course we don't know of any proof that $P \ne NP$; that is a famous open question.

For similar reasons, there is no decision problem that is known to be in $NP \setminus coNP$.

The closest we have is the following: we know of decision problems that are in $NP \setminus coNP$, if $NP \ne coNP$. For instance, if $NP \ne coNP$, then SAT is in $NP \setminus coNP$. (You can replace SAT with any other problem that is known to be NP-complete.) It is widely conjectured that $NP \ne coNP$, so SAT is a good candidate for such a problem -- but we don't know any proof that $NP \ne coNP$ (that's another famous open problem).

We can also say that if $NP = coNP$, then there is no decision problem in $NP \setminus coNP$. From this plus the above discussion, we obtain the following useful fact:

There is a problem in $NP \setminus coNP$ if and only if $NP \ne coNP$. If there is any problem in $NP \setminus coNP$, then SAT is one such problem.

The same remains valid if you replace SAT with any other NP-complete problem. Symmetrically, we also know:

There is a problem in $coNP \setminus NP$ if and only if $NP \ne coNP$. If there is any problem in $coNP \setminus NP$, then TAUTOLOGY is one such problem.

You can replace TAUTOLOGY with any other problem known to be coNP-complete.

So, this is pretty much a complete characterization of those classes, up to our lack of knowledge whether $NP=coNP$ or not.

$\endgroup$

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.