HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Proof that $NP \cap coNP = P$

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
conpcapthatproof

Problem

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

Solution

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.

Context

StackExchange Computer Science Q#165456, answer score: 5

Revisions (0)

No revisions yet.