[Solved]: What do complexity classes look like, if we use Turing reductions?

Problem Detail: 

For reasoning about things like NP-completeness, we typically use many-one reductions (i.e., Karp reductions). This leads to pictures like this:

(under standard conjectures). I'm sure we're all familiar with this sort of thing.

What picture do we get, if we work with Turing reductions (i.e., Cook reductions)? How does the picture change?

In particular, what are the most important complexity classes, and how do they relate? I am guessing that $P^{NP}$ plays the role that used to be taken up by $NP$ and $coNP$ (because $P^{NP}$ is closed under Turing reductions in the same way that $NP$ is closed under Karp reductions); is that about right?

So should the picture look like $P \subset P^{NP} \subset PH \subset PSPACE$ now, i.e., something like the following?

Is there some new sequence that plays a role that corresponds to the polynomial hierarchy? Is there a natural sequence of complexity classes $C_0=P$, $C_1=P^{NP}$, $C_2=?$, ..., such that each complexity class is closed under Turing reductions? What is the "limit" of this sequence: is it $PH$? Is it expected that each class in the sequence is different from the previous one? (By "expected", I mean under plausible conjectures, similar to the sense in which it is expected that $P \ne NP$.)

---

Related: Many-one reductions vs. Turing reductions to define NPC. That article explains that the reason we work with Karp reductions is that it gives us a finer-grained, richer, more precise hierarchy. Essentially, I am wondering what the hierarchy would look like if we worked with Turing reductions: what the coarser, less rich, less precise hierarchy would look like.

Asked By : D.W.

Answered By : Kaveh

You can use $\mathsf{P}^{\Sigma^\mathsf{P}_i}$. Some authors denote them by $\square^\mathsf{P}_i$ (similar to $\Delta^\mathsf{P}_i$ and $\nabla^\mathsf{P}_i$ notations). It's essentially the Turing closure of the polynomial hierarchy. We have $$\mathsf{P}^{\Sigma^\mathsf{P}_i}\subseteq \mathsf{NP}^{\Sigma^\mathsf{P}_i}= \Sigma^\mathsf{P}_{i+1}\subseteq \mathsf{P}^{\Sigma^\mathsf{P}_{i+1}}$$ Therefore $\mathsf{P^{PH}} = \sum_{i\geq 0}\mathsf{P}^{\Sigma^\mathsf{P}_i} = \sum_{i\geq 0}\Sigma^\mathsf{P}_{i} = \mathsf{PH}$.

If the polynomial hierarchy does not collapse all inclusions are strict.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/27703

3.2K people like this

 Download Related Notes/Documents