MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 20 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|cite|improve this answer
1  
Thanks for the great answer! – Liron Oct 24 '09 at 9:52

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

share|cite|improve this answer
    
The zoo has moved and old links broke. New link: complexityzoo.uwaterloo.ca/Complexity_Zoo:D#delta2p – mak Jan 5 at 13:35

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|cite|improve this answer
16  
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

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|cite|improve this answer

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.

share|cite|improve this answer

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.