4
$\begingroup$

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?

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This is a much more simple proof. I don't understand why did my professor had to complicate things like that... :| $\endgroup$ – so.very.tired Jun 21 '14 at 8:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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