Fake Proof that $\mathrm{NP}^\mathrm{NP} = \mathrm{NP}$

Question

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!

Answer 1

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.

Answer 2

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.

Answer 3

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.