What do we know about $NP \cap co-NP$?

• 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)

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.

StackExchange Computer Science Q#41476, answer score: 9