0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Therefore NP=coNP. Although I am not a complexity expert, this is false to me. Try providing an argument for that also. $\endgroup$ – bellpeace Aug 16 '14 at 17:22
  • 2
    $\begingroup$ Of course there's a problem with it! Even without reading what you wrote, it's very, very, very unlikely that you really managed to solve one of the most important open problems in theoretical CS in a single paragraph using techniques that any undergraduate should know about. $\endgroup$ – David Richerby Aug 16 '14 at 17:45
  • 2
    $\begingroup$ You are claiming to have a solution for a well-known, difficult open problem. This is an extraordinary claim requiring extraordinary evidence. You have not provided such so there is not much to talk about. Even if you had, this would not be a good post for SE; it is not our goal here to make broad advances to science in a single post. See here for a related discussion. $\endgroup$ – Raphael Aug 16 '14 at 18:32
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ While it's nice that both attempt and counter-argument are short, we should be careful to encourage the posting of P-vs-NP attempts for verification. $\endgroup$ – Raphael Aug 16 '14 at 18:33
  • 1
    $\begingroup$ @Raphael. Is there a "not" missing from your comment? $\endgroup$ – Rick Decker Aug 16 '14 at 18:59
  • $\begingroup$ @RickDecker Ah, prepositions and false friends. Yes, we don't want to encourage this. Thanks! $\endgroup$ – Raphael Aug 17 '14 at 8:42

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.