6
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ @vadim123 I think the OP doesn't talk about verifying solution, but about deciding. $\endgroup$
    – Xoff
    Dec 29 '13 at 22:01
  • $\begingroup$ Why do you ask that question ? In what context did you encounter that problem ? $\endgroup$
    – Xoff
    Dec 29 '13 at 22:02
  • $\begingroup$ @Xoff: I was just reading about the polynomial hierarchy and I came across P^NP and I was like "why isn't this just NP" $\endgroup$
    – Jessica
    Dec 30 '13 at 5:03
10
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Got it, thanks! $\endgroup$
    – Jessica
    Dec 30 '13 at 5:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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