Syntactic Complexity Class ${\bf X}$ such that ${\bf PP} \subseteq {\bf X} \subseteq {\bf PSPACE}$

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}$ ?

• 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... May 16, 2013 at 23:55
• @JoshuaGrochow Thanks! How about if ${\bf P} = {\bf PP}$ but ${\bf P} \neq {PSPACE}$. Can we get another class by Ladner? May 17, 2013 at 16:08
• 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$. May 18, 2013 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.
• I specifically say non-relativized... There is also ${\bf\#P} \cup {\bf \#NP} \cup ...$ May 17, 2013 at 14:24
• @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? May 18, 2013 at 16:13