I'm looking for a proof to the claim stated in the title:
if $L\in NP\cap Co-NP$ is $NP$-Hard, then $NP=Co-NP$.
I read the proof from my professor's recitation, but couldn't understand it, and I was hoping to find more easy-to-understand version of that proof.
It goes something like that:
Let $L\in NP\cap Co-NP$ be an $NPH$ problem, and let $L'\in Co-NP$, our goal is to first show that $L'\in NP$.
We know that there exist a Cook reduction from $L'$ to $\bar{L'}$ (any problem can be reduced to its complement with Cook reduction), and since $\bar{L'}\in NP$, we also know that there exist a Karp reduction from $\bar{L'}$ to $L$.
So by transitivity, we have a reduction from $L'$ to $L$.
The only problem is, $NP$ is not closed under Cook reduction (if a problem $A$ can be reduced to a problem $B\in NP$ with Cook reduction, that doesn't mean that $A\in NP$...)
So define the relation $R_{L'}$, associated with $L'$ (meaning $R_{L'}$ is the search problem of $L'$) as follows:
$R_{L'}=\left\{(x,[(z_1,\sigma_1,w_1),(z_2,\sigma_2,w_2),...(z_t,\sigma_t,w_t)]) \right\}$
Now if we can prove that $R_{L'}$ can be decided with a deterministic polynomial verifier, and that for all $(x,y)\in R_{L'}$, $|y|\leq p(|x|)$ for some polynomial $p$, we're done, and that will prove that $L'\in NP$...
Now comes the part where I really lost him, he starts to rattle on and on about "questions" and "answers", and I completely lost track.
Can anyone provide a link that explains the rest of that proof more clearly?
1 Answer
Suppose $L$ is an NP-hard problem in coNP, and let $M$ be any problem in NP. Since $L$ is NP-hard, there is a polytime reduction $f$ such that $x \in M$ iff $f(x) \in L$. Since $L$ is in coNP, this gives a coNP algorithm for $M$: given an input $x$, compute $f(x)$ and apply the coNP algorithm for $L$. This shows that $M$ is in coNP. In other words, NP is a subset of coNP. The same argument also shows the reverse inclusion, and so NP equals coNP.
The key idea is to avoid Cook reductions, for the reasons you mention.
-
1$\begingroup$ This is a much more simple proof. I don't understand why did my professor had to complicate things like that... :| $\endgroup$ Commented Jun 21, 2014 at 8:05