patternMinor
Proof that $NP \cap coNP = P$
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$.
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.
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.