Faulty proof of polynomial hierarchy first level collapse?

Question

I am an undergraduate of CS and I participate in TCS.SE. I am having trouble finding the error in a proof about the polynomial hierarchy collapsing to the first level ($NP = coNP$). I believe the reasoning to be false, because it is very simple and it would be common knowledge, however it is not.

Let $M$ be any oracle TM in $NP^{NP}$ (i.e. $ \Sigma^{P}_{2} $ ) . Obviously, by ignoring its oracle, $M$ can solve any problem in NP.

On the other (and most important) direction, let $M'$ be a TM where instead of using the oracle, we encode it into a simple non-deterministic machine with a running time of $NTIME( k(n) )$. If $M$ had a running time of $NTIME( p(n) )$ , $M'$ will have a running time of $NTIME( p(n)*k(n) )$ which is polynomial. Therefore, for any oracle TM in $NP^{NP}$, there is a non-deterministic TM that can solve the same problem in polynomial time. It follows that $NP^{NP} /subset NP$.

By combining the two statements we have that $NP=NP^{NP}$ and extending this, $NP=coNP=P^{NP}=NP^{NP}$ and the polynomial hierarchy collapses to the 1st level.

Where is the error in the above proof?

Answer 1

If you combine an NP oracle with an NP machine you don't get another NP machine. The easiest way to see that is to query the oracle once and answer the negation - this machine is clearly co-NP rather than NP.

If you take a general $NP^{NP}$ machine, you need to quantify both existentially and universally. This is very lucidly explained in these lecture notes.

Answer 2

If you want to convert the $NP^{NP}$ TM to a $NP$ TM you have to check every oracle answer in a $NP$ machine. For 'Yes' answers this is easy because it is a $NP$ oracle. But if you want to check a 'No' answer you have to check that for every nondeterministic choice within the oracle machine the answer is 'No'. This can't work unless $NP = coNP$.