This question already has an answer here:

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?


marked as duplicate by David Richerby, Nicholas Mancuso, D.W., Juho, Luke Mathieson Mar 25 '15 at 1:19

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\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).

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