It is known that some (non-relativized) syntactic complexity classes between ${\bf P}$ and ${\bf PSPACE}$ have the following property, ${\bf P} \subseteq {\bf CoNP} \subseteq {\bf US} \subseteq {\bf C_=P} \subseteq {\bf PP} \subseteq {\bf PSPACE}$. I am wondering if there exists a (non-relativized) syntactic complexity class ${\bf X}$ such that ${\bf PP} \subseteq {\bf X} \subseteq {\bf PSPACE}$? What are the implications of existence or non-existence of complexity class ${\bf X}$ ?

  • 7
    $\begingroup$ First, presumably you want a class which is believed to lie strictly between PP and PSPACE? Otherwise PP itself works, as does PSPACE. Second, it's difficult to talk about the implications of the existence of such a complexity class unless you specify what counts as a complexity class. For example, if PP \neq PSPACE, then by Ladner there is a language L in PSPACE that is PP-hard and not PSPACE-complete. If we take the closure of L under many-one reductions, the resulting "class" satisfies your question. But clearly this has no additional consequences beyond PP \neq PSPACE... $\endgroup$ – Joshua Grochow May 16 '13 at 23:55
  • 1
    $\begingroup$ @JoshuaGrochow Thanks! How about if ${\bf P} = {\bf PP}$ but ${\bf P} \neq {PSPACE}$. Can we get another class by Ladner? $\endgroup$ – Tayfun Pay May 17 '13 at 16:08
  • 1
    $\begingroup$ Yes. Same thing. Ladner's construction is very general: for any two languages $A \lneq_m^p B$ it gives a language $A \lneq_m^p C \lneq_m^p B$. $\endgroup$ – Joshua Grochow May 18 '13 at 16:09

One such class is the counting hierarchy $\mathsf{CH}$. It is defined as the union of a hierarchy that is defined similarly to the polynomial hierarchy:

  • $\mathsf{C}_{0}\mathsf{P} := \mathsf{PP}$,
  • $\mathsf{C}_{i+1}\mathsf{P} := \mathsf{PP}^{\mathsf{C}_{i}\mathsf{P}}$
  • $\mathsf{CH} := \bigcup_i \mathsf{C}_{i}\mathsf{P}$

The counting hierarchy has a nice syntactic characterization due to H. Vollmer and K. Wagner "Recursion theoretic characterizations of complexity classes of counting functions", Theoretical Computer Science 163:245-258, 1996: $\mathsf{CH}$ ist the set of $0$-$1$-valued functions in the closure of basic arithmetic functions $0,1,+,-,\cdot$ under composition and bounded sums.

| cite | improve this answer | |
  • $\begingroup$ I specifically say non-relativized... There is also ${\bf\#P} \cup {\bf \#NP} \cup ... $ $\endgroup$ – Tayfun Pay May 17 '13 at 14:24
  • 6
    $\begingroup$ @TayfunPay: The final paragraph shows that $CH$ can be given a characterization without the use of oracles...what, precisely, do you mean by "non-relativized" then? Do you want a "non-oracle machine" characterization"? A leaf language characterization? $\endgroup$ – Joshua Grochow May 18 '13 at 16:13
  • 2
    $\begingroup$ It is indeed correct. Ok $\endgroup$ – Tayfun Pay Oct 21 '14 at 15:45

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.