Characterize P^NP (a.k.a. Delta_2^p)

Question

What can you say about the complexity class $\text{P}^{\text{NP}}$, i.e. decision problems solvable by a polytime TM with an oracle for SAT? This class is also known as $\Delta_2^p$.

Obviously $\text{P}^{\text{NP}}$ is in $\text{PH}$ somewhere between $\text{NP} \cup \text{coNP}$, and $\Sigma_2^p \cap \Pi_2^p$. What else is known about that complexity class?

Answer 1

The standard complete problem for the "function version" of P^NP is to find the lexicographically last satisfying assignment of a given boolean formula. To be more finicky, a complete language for P^NP is

{ n-variable boolean formulas phi : phi is satisfiable and phi's lexicographically last satisfying assignment has x_n = 1 }.

This is Krentel's Theorem.

Under a standard complexity assumption one can derandomize the more powerful class BPP^NP down to P^NP. With the power of BPP^NP, one can compute the number of satisfying assignments to a circuit to within a 1 +/- 1/poly(n) factor [Sipser / Stockmeyer / Valiant-Vazirani] and exactly learn unknown polynomial-size circuits [Bshouty-Cleve-Gavalda-Kannan-Tamon].

Answer 2

Here is another interesting characterization of $P^{NP}$. I found it as an undergrad but could not publish it; it turned out to be a "folklore" result. It is entertaining nevertheless, and you will learn something about $P^{NP}$ by reproving it for yourself. We will define a natural deterministic model of computation whose class of recognized languages will be $P^{NP}$.

A machine $M$ in our model is described as follows. We take a polynomial time Turing machine which on an input of length $n$, is granted access to a bit counter that holds $n^k$ bits, for some fixed $k$. Initially the counter is all zeros. Along with the usual start, accept and reject states, the Turing machine has a special extra state called increment, with the following properties:

• If the Turing machine enters the increment state, the counter is incremented by $1$, and the Turing machine resets to its initial starting configuration. That is, all the workspace used by the machine is reset to blanks, all tape heads move back to the beginning of the tapes, and the machine switches to its start state.
• If the Turing machine reaches accept or reject, the entire process halts with this result.
• If the counter reaches all-ones, the process rejects.

This is a natural way to characterize brute-force search for an NP solution: the counter represents the search space, and we run a specific polytime Turing machine that tests each counter value in turn until we decide to accept or reject.

Theorem: The class of all languages recognized by such $M$ is exactly $P^{NP}$.

Good luck with the proof. Here is a hint: one direction is easy, by Ryan O'Donnell's comment on complete languages for $P^{NP}$.

Answer 3

This class is also known as Δ₂P. See the complexity zoo for more details and results.

Answer 4

András Salamon's answer to a similar question on cs.stackexchange.com named some additional $P^{NP}$-complete problems.

Krentel also gave another problem besides the one mentioned by Ryan O'Donnell:

Input: Weighted graph $G$, integer $k$.
Question: Is the length of the shortest TSP tour in $G$ divisible by $k$?

Before him, Papadimitriou had already found:

Input: An instance of the TSP (that is, an $n \times n$ symmetric distance matrix of nonnegative integers) Question: Is there a unique shortest TSP tour?

According to Krentel, this was the only known $P^{NP}$-complete problem before his work.

• Mark W. Krentel, The Complexity of Optimization Problems, JCSS 36 490–509, 1988. doi:10.1016/0022-0000(88)90039-6
• Christos H. Papadimitriou, On the Complexity of Unique Solutions, JACM 31:2, 1984. doi:10.1145/62.322435

Answer 5

I think MAX_CLIQUE_SIZE is in $P^{NP}$. Class of problems that are Cook-reducible to $NP$ problems. Something closely related was in one Open Question submitted from my actual computation complexity prof :)