# 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".

• mathoverflow.net/questions/2218/characterize-pnp Sep 10, 2013 at 18:03
• I wonder whether this question should not be moved to cstheory.stackexchange.com Sep 11, 2013 at 13:31
• Indeed, there is a confusing overlap between cs.stackexchange.com, cstheory.stackexchange.com, and mathoverflow.net. Would be good to clarify this somewhere. Anyway, I agree that moving would be better.
– mak
Sep 11, 2013 at 17:35

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