Question

What can you say about the complexity class P^NP, i.e. decision problems solvable by a polytime TM with an oracle for SAT?

Obviously P^NP is in PH somewhere between NP union coNP, and Sigma2 intersect Pi2. 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

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

Answer 3

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 4

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 :)