Simple interepretation problem regarding Polynomial Hierarchy?

Question

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?

Answer 1

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.

Answer 2

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).

Answer 3

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