Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

4 Answers

up vote 18 down vote accepted

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

share|improve this answer
1  
Thanks for the great answer! –  Liron Oct 24 '09 at 9:52
add comment

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

share|improve this answer
add comment

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

share|improve this answer
15  
It seems that $P^{NP}$ is best characterized by people named Ryan. –  Greg Kuperberg Dec 16 '09 at 6:52
    
I suppose that incrementing also restarts the "polynomial time" clock? –  Max Dec 14 '10 at 10:51
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.