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

  • 3
    $\begingroup$ mathoverflow.net/questions/2218/characterize-pnp $\endgroup$
    – sdcvvc
    Sep 10 '13 at 18:03
  • 1
    $\begingroup$ I wonder whether this question should not be moved to cstheory.stackexchange.com $\endgroup$
    – J.-E. Pin
    Sep 11 '13 at 13:31
  • 1
    $\begingroup$ 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. $\endgroup$
    – mak
    Sep 11 '13 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$.


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.