Problem Detail: 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”.
Asked By : mak
Answered By : András Salamon
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 http://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
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/14251 Ask a Question Download Related Notes/Documents
