I found this faulty proof of $$ \newcommand{\NP}{\mathrm{NP}} \NP = \NP^{\NP}, $$ where the tricky part is to proof that $ \NP ^{\NP} \subseteq \NP$, and this is how it is realized:

Take $\NP^\NP$ machine that is a ND polytime TM1 running in $O(P_1(n))$ and assume the oracle as a ND polytime TM2 running in $O(P_2(n))$. Replace the oracle with actual calls to TM2, so $\NP^{\NP}$ machine is TM3 that is non-deterministic running in $O(P_1 \cdot P_2(n))$. This is in fact an NP machine, thus $\NP^\NP \subseteq \NP$.

Could anyone help me? I can't figure out the error. Thank you!

  • 1
    $\begingroup$ It is disturbing to hear that you found that statement as an "exercise" - can you tell us where? A common belief is that $NP \neq NP^{NP} = \Sigma_2^p$ (though this is still just a conjecture, of course). $\endgroup$ – Srivatsan Oct 31 '11 at 18:10
  • $\begingroup$ @Srivatsan: Actually I found it googling ... I know that it's a conjecture but the real exercise is to understand the conceptual error in this faulty proof: that's the real effort. Thanks for your editing... J. $\endgroup$ – Josh Vorney Oct 31 '11 at 20:38
  • $\begingroup$ My intuition, from what I've understood, is the following: the faulty part is the sentence "This is in fact an NP machine", since I could obtain a co-NP machine simply reverting the output of the oracle. So this means that it would be true iff NP = co-NP. Am I wrong? Thanks. $\endgroup$ – Josh Vorney Nov 1 '11 at 7:58

The problem is that queries to TM2 do not return a single answer. Instead, the subroutine results in a branching of the computation, without any way to combine branches before the computation ends.

Consider the co-NP language UNSAT (the negation of SAT). The $NP^{NP}$ oracle algorithm is trivial -- query the SAT oracle and return the opposite.

We now try to replace the SAT oracle with an actual TM2 that guesses solutions and checks if the satisfy the given formula. Note that TM1 no longer gets a cleanly-packaged solution. Instead, it has to handle each branch of the sub-computation individually.

Let's run through what happens on input $\phi$.

If a branch of the query returns "YES", then THAT BRANCH knows that $\phi$ is satisfiable and so knows to return a final answer of "NO".

But what if a branch of the query returns "NO"? That branch doesn't know the true status of $\phi$. It could assume that the true answer is "NO" and therefore accept, but that causes the overall computation to accept -- incorrect behavior if $\phi$ was actually satisfiable.

The other option is to abort the "NO branch of the query since it doesn't have enough information to go on. But suppose that $\phi$ is actually unsatisfiable. Then every branch aborts, and the machine (incorrectly) rejects.

  • $\begingroup$ Thanks for your clear answer! But, what can I say about the correctness of this part : "TM3 is non-deterministic running in O(P1⋅P2(n)). This is in fact an NP machine"? I've understood that replacing oracle with actual calls can lead to wrong answer, but does it imply that TM3 cannot be constructed? Thanks. $\endgroup$ – Josh Vorney Nov 2 '11 at 9:01
  • $\begingroup$ Correct. You can express a non-deterministic TM via standard source code, augmented with a magic "GUESS" function. Similarly, you can express an oracle machine via a magic "QUERY" function. Given the source code for TM1 and TM2, you can replace each call to QUERY in TM1 with the code for TM2. However, as discussed, the resulting code will be incorrect. $\endgroup$ – Jeremy Hurwitz Nov 3 '11 at 22:27

The problem is with "actual calls to TM2". You are trying to build a nondeterministic Turing machine which accepts on the language accepted by TM1. The only way to call TM2 is to jump to a state of TM2 and perhaps do extra processing after the accepting state of TM2. But then you can only continue if TM2 accepts - not if TM2 has no accepting paths. TM1 is allowed to ask "does TM2 accept on input x?". It can then do further processing even if TM2 did not accept x.

  • $\begingroup$ I really don't get what you mean, I had another idea that I've explained in the comment above... $\endgroup$ – Josh Vorney Nov 1 '11 at 16:27

Short answer: You can replace the oracle questions with an NP machine. The result is not an NP machine.

Longer answer: The question a machine can ask from an oracle have various types and each is a different kind of reduction. The most general form which is arbitrary use of the oracle gives Turing (T) reducibility. Many-one (m) reducibility is when we can ask a question from the oracle and only one question and we will return the answer of the oracle as our answer, no post processing. There are other kinds of reductions, e.g. truth-table (tt) which is a nonadaptive use of oracle (questions from the oracle cannot depend on previous answers from the oracle).

We can just talk about $P^{NP}$ since it is the same as $NP^{NP}$. So the question is why $P^{NP}$ cannot be turned into a $NP$ machine. The answer is the kind of access to the oracle. For example, if we can do post processing, with a single query to an $SAT$ we can solve the $coNP$-complete problem TAUT. If you restrict the access to the oracle in the right way then you can prove the machine is equivalent to an $NP$ machine. One way of doing it is one question, and that is the answer of the machine restriction.


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.