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?

up vote 4 down vote accepted

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.

  • Thanks a lot. Those notes were spot-on. – chazisop Mar 18 '11 at 2:29

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

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.