10
$\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.

$\endgroup$
  • $\begingroup$ We may have some information spread out over several questions. $\endgroup$ – Raphael Jun 14 '14 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$ – vzn Jun 14 '14 at 15:26
  • $\begingroup$ Thanks, @Raphael, I've reviewed all of those, and I don't think they answer any of my questions. $\endgroup$ – D.W. Jun 14 '14 at 16:36
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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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