Why is NP not equal to P^NP?

Question

If something can be decided in polynomial time with an NP oracle, why isn't it in NP? You would think that if you ran a polynomial-time nondeterministic Turing machine polynomially many times, that would only increase its effort by a polynomial time multiplier, which means the problem could be solved by a nondeterministic Turing machine in polynomial time.

Answer 1

Actually, it is possible that $\mathrm{NP}=\mathrm{P}^{\mathrm{NP}}$, it's even possible that the whole Polynomial Hierarchy collapses down to $\mathrm{P}$ (which would happen if, and only if, $\mathrm{P}=\mathrm{NP}$)!

The correct question should thus say "Why is not obviously true that $\mathrm{NP}=\mathrm{P}^{\mathrm{NP}}$?". The answer is related to how $\mathrm{NP}$ works when it is used directly versus being used as an oracle.

One of the weaknesses of $\mathrm{NP}$ is negation. In order for a problem to belong to $\mathrm{NP}$, there needs to be some polynomial-time deterministic algorithm $A$ which must have two properties:

• For every "positive" instance, it must be possible to find a witness which can be used to convince $A$ that answer of the problem is indeed "yes".
• For every negative instance, no such witness can be used to fool $A$ into thinking the answer is "yes".

Note the asymmetry, "yes" instances ask for just a single witness, but "no" require that none exist.

As a specific example, consider the problem SAT = satisfiability of propositional formula. It's easy to see that for each satisfiable formula, any satisfying assignment of the variables can be used as the witness and if $A$ works by checking if the assignment provided indeed satisfies the given formula, it cannot be fooled by any fake would-be-witnesses. Thus, the SAT problem is certainly in $\mathrm{NP}$.

However, can you think of any way how to produce polynomial-time-checkable witnesses (and the corresponding checker $A$) for the problem UNSAT, which asks whether a formula is not satisfiable? At the moment, nobody knows how to do that, or whether it even is possible [if you can do it, write it down and you'll be famous :-) ]

Now, if we have an $\mathrm{NP}$ oracle, this all is hidden from us; we just get a magic box which correctly answers "yes" or "no" for the satisfiability problem (which we have shown to be in $\mathrm{NP}$). We can simply hand it the formula and ask "Is this one satisfiable?" and just output the negation of what it says. Bang, we've just proved that UNSAT belongs to $P^\mathrm{NP}$ (in fact, we used the oracle just once).

Thus, we know that $\mathrm{NP}\subseteq \mathrm{P}^\mathrm{NP}$, but whether the inclusion is strict remains an open question. In fact, this also explains why the class $\mathrm{co-NP}$ (which consists of complements of $\mathrm{NP}$ problems; i.e. problems when witness is required for "no" and its non-existence is needed for "yes" instances) actually is interesting.