# Proof that $NP \cap coNP = P$

Suppose I want to prove that $$NP \cap coNP = P$$. Since clearly $$P\subseteq NP \cap coNP$$, I need to prove the opposite direction, i.e., every problem in $$NP \cap coNP$$ has a polynomial-time algorithm. Is there a shorter way to prove this equality than arguing about all problems in $$NP \cap coNP$$?

One obvious way would be to find a polynomial-time algorithm for SAT, since this would imply $$P=NP$$ and therefore also $$NP \cap coNP = P$$. But I am looking for an easier way.

In particular, is there a problem $$X$$ that is not NP-complete, but complete for $$NP \cap coNP$$? If such a problem exists, then an algorithm for $$X$$ would imply $$P\subseteq NP \cap coNP$$.

• Given that $\textit{NP}=\textit{coNP}$ is still an open problem, and given that that would imply $\textit{NP}\cap\textit{coNP}=\textit{NP}$, contradicting your proposition unless $\textit P=\textit{NP}$, I would not expect a simple proof for your proposition to exist; it may likely even be false.
– fuz
Commented Feb 8 at 19:06
• @fuz Sure. I am not claiming that $NP\cap coNP=P$ necessarily holds. I just want to understand what would constitute a valid proof for this. Commented Feb 8 at 19:14
• Meanwhile, I assume a satisfability problem with the promise "$\varphi$ is satisfiable or has a polynomial time verifiable refutation" would be complete for promise-$NP\cap coNP$. Commented Feb 9 at 12:44
• Basically, as I see it, $P=NP\cap coNP$ would also imply $P=NP$, as for both an algorithm that works in polynomial time only on satisfiable instances would suffice. And a similar logic goes for any other complexity class that is closed under complement, not just $P$. Commented Feb 9 at 12:58

As mentioned by D.W., asking for a complete problem for $$\mathrm{NP} \cap \mathrm{coNP}$$ is going to be messy. However, for the purpose of "Can I work on a polytime algorithm for this concrete problem in an attempt to prove $$\mathrm{NP} \cap \mathrm{coNP} = \mathrm{P}$$?", we do have options available to us. We just need to look beyond total decision problems.

For example, consider the following computational problem $$A$$: Given two $$\mathrm{SAT}$$-instances $$\phi_0,\phi_1$$ subject to the promise that exactly one of them is satisfiable, decide which one is.

Or, if you prefer multivaluedness over partiality, we can consider the problem $$B$$ defined as: Given two $$\mathrm{SAT}$$-instances $$\phi_0,\phi_1$$, compute some $$i \in \{0,1\}$$ such that if $$\phi_{1-i}$$ is satisfiable, then so is $$\phi_i$$.

Claim: A total decision problem is polytime many-one reducible to $$A$$ if and only if it is polytime many-one reducible to $$B$$ if and only if it belongs to $$\mathrm{NP} \cap \mathrm{coNP}$$.

So, a polytime algorithm for $$A$$ (or equivalently, $$B$$) implies $$\mathrm{NP} \cap \mathrm{coNP} = \mathrm{P}$$, and in some sense, is not much stronger than it.

• So why are problems A and B not called "complete for $NP\cap coNP$"? Is it just because they are formally not total decision problems? Commented Feb 10 at 18:50
• @ErelSegal-Halevi Exactly.
– Arno
Commented Feb 10 at 18:54

So far we don't know of any problem that can be proven to be complete for $$NP \cap coNP$$. See https://cstheory.stackexchange.com/q/49/5038 and https://mathoverflow.net/q/34889/37212 for extended discussion of some of the challenges, related results, and a few entry points into the literature.