3
$\begingroup$

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$.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – fuz
    Feb 8 at 19:06
  • $\begingroup$ @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. $\endgroup$ Feb 8 at 19:14
  • $\begingroup$ 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$. $\endgroup$
    – rus9384
    Feb 9 at 12:44
  • $\begingroup$ 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$. $\endgroup$
    – rus9384
    Feb 9 at 12:58

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ Feb 10 at 18:50
  • $\begingroup$ @ErelSegal-Halevi Exactly. $\endgroup$
    – Arno
    Feb 10 at 18:54
3
$\begingroup$

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.

Related: What do we know about $NP \cap co-NP$?, Complete problems in NP∩coNP.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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