So in this paper I'm reading (https://adamsmith.as/papers/fdg2013_shortcuts.pdf), the authors talk about an $NP^{NP}$-complete problem, in relation to Answer Set Programming. I know what P, NP, etc. are but I don't unerstand what they mean with $NP^{NP}$. Also I can't Google it because Google doesn't recognize superscript.

I did find out it's also mentioned in this book, but they still don't provide an explanation.

Can anyone ecplain this class of problems to me?

  • $\begingroup$ $NP^{NP}$ is the set of languages in which you can query any language in $NP$ in constant time (by invoking an "oracle"), that are also checkable in polynomial time (definition of $NP$). Similarly, $P^{NP}$ is the set of languages solvable in polynomial time while also having access to an oracle that can decide membership in any language in $NP$ in constant time. $\endgroup$ – Ryan Mar 24 '15 at 20:58

$NP$ is the class of problems that, roughly speaking, you can solve by guessing an $y$ of polynomial size (with some magic to guarantee that you guess "right") and then doing a polynomial computation involving $y$ and the original input.

$NP^{NP}$ is the class of problems solvable in this way, if you have access to an oracle for $NP$. After guessing $y$, you're not just allowed to do some polynomial computation, you're also allowed (within this calculation) to solve problems from $NP$ (through an oracle, so in constant time).

The classical $NP$-complete problem of boolean satisfiability is to compute $\exists_x R(x)$ where $R$ is some boolean formula (and $x$ is a shorthand for $x_1,\ldots,x_n$). Its $NP^{NP}$-complete analogue is to compute $\exists_x \forall_y R(x)$.

A slightly more intuitive $NP^{NP}$-complete problem is that of formula minimization: given a formula, can you find a formula of length $\leq k$ that expresses the same (boolean) function?

$NP^{NP}$ is also known as $\Sigma_2 P$, and you will be able to find more info by searching for "polynomial hierarchy" (see, e.g., Wikipedia's article).

| cite | improve this answer | |
  • $\begingroup$ Thank you for the explanation! So would it be acceptable to say that $NP^{NP}$-complete problems can be verified in polynomial time, if you had a black box that could solve $NP$-complete problems? Or did I misunderstand? $\endgroup$ – Wouter Florijn Mar 24 '15 at 21:15

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