Which problems are hard for P^NP?

Quantified Boolean formulae are the prime examples of problems that are hard for the polynomial hierarchy, i.e., for the $\Pi$ and $\Sigma$ versions of it. However, there is also the $\Delta$ version, defined as $\Delta_{i+1}^{\rm P} := {\rm P}^{\Sigma_i^{\rm P}}$. In particular, $\Delta_2^{\rm P} = {\rm P}^{\rm NP}$.

What are typical hard problems for this part of the hierarchy?

I failed to search the Web for this; especially, you cannot use Google to find much about "P^NP".

Krentel gave two problems complete for $\Delta_2^P$ (see Theorem 3.4):

Input: Boolean formula $\phi(x_1,\dots,x_n)$.

Question: Is $x_n = 1$ in the lexicographically largest satisfying assignment of $\phi$?

Input: Weighted graph $G$, integer $k$.

Question: Is the length of the shortest TSP tour in $G$ divisible by $k$?

Krentel also states that the only previous example of a $\Delta_2^P$-complete problem up to 1988 was Uniquely Optimal TSP, given by Papadimitriou in 1984.

As sdcvvc pointed out, see also the MO discussion at https://mathoverflow.net/questions/2218/characterize-pnp for a nice discussion by Ryan Williams of a machine model that captures $\Delta_2^P$.

• Mark W. Krentel, The Complexity of Optimization Problems, JCSS 36 490–509, 1988. doi:10.1016/0022-0000(88)90039-6

StackExchange Computer Science Q#14251, answer score: 6