Cheap and Secure Web Hosting Provider : See Now

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

, ,
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.

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).