Cheap and Secure Web Hosting Provider : See Now

[Solved]: Problem with my proof that NP = coNP?

, , No Comments
Problem Detail: 

Is there a problem with this proof that NP = coNP?

It suffices to show that Satisfiability can be solved efficiently with at most a polynomial number of queries to an oracle for Tautology. The algorithm for a problem P is, pick a variable X in P and fix it to T to obtain a problem P'. Submit ~P' to the oracle for Tautology. If ~P' is a tautology, then X is a "no go" for the problem P. If the oracle accepts ~P', then fix X to T in the result, otherwise fix X to F. Then proceed to the next variable. This requires linear queries in the size of the problem. An analogous result reduces Tautology to Satisfiability. Therefore NP = coNP.

My only doubt is that maybe when you're using an oracle you only get to find out if it accepts, not if it rejects. That would block this proof.

Asked By : user2817408

Answered By : Shaull

You are confusing Turing reductions with mapping reduction, in a sense. The problem with your argument is that if you allow an oracle $O$ to an NP-complete (or coNP-complete) problem, you immediately get that $P^O=co-P^O$. That is, if you already have an oracle for coNP, then you cannot distinguish NP from coNP (but that does not mean that they are equal!).

Here is a shorter version of your argument, to make things clear: suppose we have an oracle for Tautology. It is true that $\phi$ is satisfiable iff $\neg \phi$ is not a tautology. Thus, in order to test if $\phi$ is satisfiable, just run the oracle on $\neg \phi$, and invert the answer. But this only shows that $NP\subseteq P^{coNP}$. Your assumption that $P^{coNP}=coNP$ is incorrect (or at least, it's an open question).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29179

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback