8
$\begingroup$

So $NP$ stands for problems where we have small verifiable witnesses for $YES$ instances and $coNP$ for small verifiable witnesses for $NO$ instances. How does this work for

  1. $P^{NP}$

  2. $NP^{NP}$

  3. $coNP^{NP}$

  4. and so on?

$\endgroup$
8
$\begingroup$

There is a logical interpretation of the various levels of the polynomial hierarchy, which extends the witness characterization of $\mathsf{NP}$ and $\mathsf{coNP}$.

A language $L$ is in $\Sigma_k^P$ if there is a polytime predicate $f$ and a polynomial $\ell$ such that $$ x \in L \Leftrightarrow \exists |y_1| \le \ell(|x|) \; \forall |y_2| \le \ell(|x|) \; \cdots Q |y_k| \le \ell(|x|) \; f(x,y_1,\ldots,y_k). $$ Here:

  • $\exists |y| \le \ell(|x|)$ means that there exists a number $y$ whose length is at most $\ell(|x|)$ such that ...
  • $\forall |y| \le \ell(|x|)$ mean that for all $y$ whose length is at most $\ell(|x|)$, the following holds ...
  • $Q$ is $\exists$ if $k$ is odd and $\forall$ if $k$ is even.

Similarly, $L$ is in $\Pi_k^P$ if it can be written in a similar way, only starting with $\forall$.

As an example, $\mathsf{NP}^{\mathsf{NP}}$ is $\Sigma_2^P$, and consists of all languages such that $$ x \in L \Leftrightarrow \exists |y_1| \leq \ell(|x|) \; \forall |y_2| \leq \ell(|x|) \; f(x,y_1,\ldots,y_k). $$ As another example, $\mathsf{coNP}^{\mathsf{NP}}$ is $\Pi_2^P$.

Your third example is $\mathsf{P}^{\mathsf{NP}}$, which is $\Delta_2^P$. I'm not sure what is the logical characterization.

$\endgroup$
  • $\begingroup$ This old MO post has a few characterisations of $\Delta_2^P$, although none seem purely logical. It may be possible to write one of them in a purely logical form. $\endgroup$ – Discrete lizard Jul 11 at 7:33
  • $\begingroup$ @YuvalFilmus Could you be more verbose on this at least for $NP^{NP}$? $\endgroup$ – T.... Jul 11 at 8:58
1
$\begingroup$

To say $\mathsf{NP}$ contains problems with "small verifiable witnesses" is conceptually inaccurate at best. The witnesses are only polynomially bounded because we want the verifier to be efficient (i.e., run in polynomial time). In such a setting, only a polynomially long prefix of any witness can be relevant, hence why we insist on polynomially long witnesses. Also, "small" potentially means constant or logarithmic; those are not used, of course, because they can be brute-forced by polynomial-time algorithms (and only give us problems in $\mathsf{P}$).

The way the proof system notion of $\mathsf{NP}$ generalizes to yield the polynomial hierarchy is much like the logical point of view that Yuval Filmus describes in his answer. Let me introduce the less technical view behind it.

We consider two-party games which are based on QBFs. An instance (or the "board" if you care to imagine it as a board game like chess or checkers) of such a game is a formula $\varphi(x_1, y_1, \ldots, x_m, y_m)$, and the two players, say $A$ and $B$, take turns choosing values for $x_i$ and $y_i$, respectively. Each such choice constitutes a move. When no more values are left, the formula (i.e., the game's final position) is evaluated; $A$ wins if it is true, and $B$ wins if it is false.

This game models existential and universal quantifiers in the following way: If the formula is a true QBF, then $A$ (which plays the role of existential quantifiers) will always have a winning strategy and be able to choose a series of $x_1, \ldots, x_m$ which cause $\varphi$ to be true regardless of the values $y_1, \ldots, y_m$ picked by $B$ (which plays the role of universal quantifiers). The "yes" instances are those in which the QBF is true, that is, $A$ always has a winning strategy, regardless of how $B$ plays.

$\Sigma_i$ and $\Pi_i$ then correspond to games which last for $i$ moves and in which $A$ and $B$, respectively, get to go first. Actually, you even get $\textsf{PSPACE}$ and the $\textsf{PH} \subseteq \textsf{PSPACE}$ inclusion as a bonus since it corresponds to the class of games which go on for an arbitrary (though predetermined) number of moves.

Note also that $\Sigma_1 = \mathsf{NP}$ and $\Pi_1 = \mathsf{coNP}$ are rather degenerate cases of these games because $B$ and $A$, respectively, do not get the chance to move at all! For example, for the "yes" instances of $\Pi_1 = \mathsf{coNP}$, $A$ gets to win simply by doing nothing (since a "yes" instance is a tautology and is true regardless of what $B$ chooses).

There is also a more generalized version of the above which is based on generic games (and not QBFs specifically). You can find it, for instance, in section 5.4 "PSPACE and Games" of Goldreich's "Computational Complexity: A Conceptual Perspective" (here is a free link to the draft version; see p. 174 as well as pp. 118–121).

$\endgroup$
  • $\begingroup$ Thank you. How does the game properties reflect $P^{NP}$, $NP^{NP}$ and $coNP^{NP}$ (like is there a short polynomial length witness for every move $A$ makes or something like that?) $\endgroup$ – T.... Jul 11 at 8:54
  • $\begingroup$ In the generic version from the Goldreich book I mentioned, you can find that we need the following specifics: 1. "each move has a description length that is bounded by a polynomial in the length of the initial position"; 2. updating the current position can be done in polynomial time (resp. to the length of the initial position); 3. determining the winner from the final position takes polynomial time. These are all fulfilled by the QBF game. $\endgroup$ – dkaeae Jul 11 at 9:00
  • $\begingroup$ "The witnesses [for NP] are only polynomially bounded because we want the verifier to be efficient (i.e., run in polynomial time)" That's not really true. Verification is in polynomial time with respect to the length of the witness so the witness is "efficiently" verifiable regardless of how long it is. We require the witness to be polynomially bounded because that corresponds to the polynomial time bound of the nondeterministic TM the witness is witnessing. $\endgroup$ – David Richerby Jul 11 at 10:38
  • $\begingroup$ @DavidRicherby Actually, for (offline) nondeterministic TMs it is immaterial whether the nondeterministic input is even bounded or not (i.e., an infinite string). In that setting, $\mathsf{NP}$ is the set of problems decidable in a polynomial amount of steps in the length of the input. That this is also a polynomial in the number of nondeterministic bits used is a (desirable) side effect. For online nondeterminism, even more so. The witness length is dictated by the time bound, not the other way around. $\endgroup$ – dkaeae Jul 11 at 11:39
  • 1
    $\begingroup$ @ThomasKlimpel Indeed, I meant $\Sigma_i$. Thanks for pointing it out. Also thanks for providing an insightful answer; I was not aware there was a (at least partially) "nice" logical characterization of $\Delta_i$ (and could not find any in literature) +1 $\endgroup$ – dkaeae Jul 16 at 11:45
1
$\begingroup$

$\mathsf{P}^{\mathsf{NP}}$ is the closure of $\mathsf{NP}$ under polynomial time Turing reductions (=Cook reductions). Therefore, it is closed under Cook reductions, so that we have $\mathsf{P}^{\mathsf{NP}}=\mathsf{P}^{\mathsf{P}^{\mathsf{NP}}}$. In fact, for any oracle $\mathsf{A}$, we define $\mathsf{P}^{\mathsf{A}}$ as the closure of $\mathsf{A}$ under Cook reductions, and we always have $\mathsf{P}^{\mathsf{A}}=\mathsf{P}^{\mathsf{P}^{\mathsf{A}}}$ and $\mathsf{NP}^{\mathsf{A}}=\mathsf{NP}^{\mathsf{P}^{\mathsf{A}}}$. Also $\mathsf{coNP}^{\mathsf{A}}=\mathsf{coNP}^{\mathsf{P}^{\mathsf{A}}}$ and $\mathsf{P}^{\mathsf{NP}}=\mathsf{P}^{\mathsf{coNP}}$. But Cook reductions feel slightly unnatural for decision problems.

Note that $\mathsf{P}$ is a function class in disguide, and that $\mathsf{P}^{\mathsf{NP}}$ too is a function class in disguise. Let us write $\mathsf{PF}$ for the class of polynomial time computable partial functions, i.e. the function class corresponding to $\mathsf{P}$, and $\mathsf{PF}^{\mathsf{NP}}$ for the function class corresponding to $\mathsf{P}^{\mathsf{NP}}$. Including the partial functions allows to use established notation (used in A taxonomy of complexity classes of functions by A. Selman, 1994) that avoids the name clash with the unrelated class $\mathsf{FP}$.

Cook reduction feel more natural for function classes. You probably encountered a Cook reduction (and implicitly also the class $\mathsf{PF}^{\mathsf{NP}}$) at the point where your text book or professor explained why it is OK to only look at decision problems. Typically, something like an algorithm (from $\mathsf{PF}^{\mathsf{NP}}$) to compute the lexicographically last satisfying assignment of a given SAT instance is described. One first asks the oracle whether there is any satisfying assignment at all, and then determines the values of the (binary) variables $x_k$ by successively asking the oracle whether there is a satisfying assignment where $x_1,\dots,x_{k-1}$ are set to the already determined values, and $x_k$ is set to $1$. If yes, then one sets $x_k$ to $1$, otherwise one sets $x_k$ to $0$. (Note that this is a partial function, since the function is undefined in case there is no satisfying assignment.)


Let me try to say some words about Yuval Filmus remark:

Your third example is $\mathsf{P}^{\mathsf{NP}}$, which is $\Delta_2^P$. I'm not sure what is the logical characterization.

There are two difficulties to overcome: (1) the characterization of a function class has a different feel than the logical characterization of a decision class, and (2) at least for $\mathsf{P}^{\mathsf{A}}$ we have to model the deterministic character of the queries to the oracle $\mathsf{A}$.

If we look at the class $\mathsf{UPF}$ of partial functions corresponding to the class $\mathsf{UP}$ of decision problems first, then we can ignore (2) for a moment: A partial function $pf$ is in $\mathsf{UPF}^{\Sigma_k^P}$ if there is a polytime partial function $p$, a polytime predicate $f$ and a polynomial $\ell$ such that $pf(x)=p(x,z)$ where $$\exists_{\leq 1} |z|\le \ell(|x|)p(x,z)\neq\bot\land\exists |y_1| \le \ell(|x|) \; \forall |y_2| \le \ell(|x|) \; \cdots Q |y_k| \le \ell(|x|) \; f(x,y_1,\ldots,y_k,z). $$ Here:

  • $\exists |y| \le \ell(|x|)$ means that there exists a number $y$ whose length is at most $\ell(|x|)$ such that ...
  • $\forall |y| \le \ell(|x|)$ mean that for all $y$ whose length is at most $\ell(|x|)$, the following holds ...
  • $Q$ is $\exists$ if $k$ is odd and $\forall$ if $k$ is even.

One could try to overcome (2) by introducing the operators $\operatorname{BIT}(z,i):=z[i]$ and $\operatorname{TRUNC}(z,i):=z\left|_{[1,i)}\right.$. But it would still get ugly, and one can argue whether this would really constitute a logical characterization.

$\endgroup$

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.