Problem Detail: I’m looking for a proof to the claim stated in the title:
if $Lin NPcap 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 $Lin NPcap 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 $Bin NP$ with Cook reduction, that doesn’t mean that $Ain 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?
if $Lin NPcap 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 $Lin NPcap 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 $Bin NP$ with Cook reduction, that doesn’t mean that $Ain 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?
Asked By : so.very.tired
Answered By : Yuval Filmus
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/27884
