Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

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.

share|improve this answer
    
Thanks a lot. Those notes were spot-on. –  chazisop Mar 18 '11 at 2:29
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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