Simple interepretation problem regarding Polynomial Hierarchy?

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

-
$P^{NP}$

-
$NP^{NP}$

-
$coNP^{NP}$

-
and so on?

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.

StackExchange Computer Science Q#111699, answer score: 8