11
$\begingroup$

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 Jun 14, 2014 at 3:00
$\endgroup$
3
  • $\begingroup$ We may have some information spread out over several questions. $\endgroup$ Commented Jun 14, 2014 at 7:24
  • $\begingroup$ from that question eg answer "they are conjectured to be distinct notions. the distinction of coNP vs NP disappears with Turing reductions." also note coNP≠NP (widely conjectured) implies P≠NP (P is closed under complement). so its tied up with some deep open complexity theory questions. $\endgroup$ Commented Jun 14, 2014 at 15:26
  • $\begingroup$ Thanks, @Raphael, I've reviewed all of those, and I don't think they answer any of my questions. $\endgroup$ Commented Jun 14, 2014 at 16:36

1 Answer 1

4
$\begingroup$

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.

answered Sep 11, 2014 at 18:11
$\endgroup$

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.