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

<ul>
<li>$\mathsf{C}_{0}\mathsf{P} := \mathsf{PP}$,</li>
<li>$\mathsf{C}_{i+1}\mathsf{P} := \mathsf{PP}^{\mathsf{C}_{i}\mathsf{P}}$</li>
<li>$\mathsf{CH} := \bigcup_i \mathsf{C}_{i}\mathsf{P}$</li>
</ul>

<p>The counting hierarchy has a nice syntactic characterization due to 
<a href="http://dx.doi.org/10.1016/0304-3975%2895%2900237-5">H. Vollmer and K. Wagner "Recursion theoretic characterizations of complexity classes of counting functions", Theoretical Computer Science 163:245-258, 1996</a>:
$\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.</p>

CC BY-SA 3.0
2013-05-17T14:24:59.477Z
I specifically say non-relativized... There is also ${\bf\#P} \cup {\bf \#NP} \cup ... $
Tayfun Pay
CC BY-SA 3.0
2013-05-18T16:13:17.977Z
@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?
Joshua Grochow
CC BY-SA 3.0
2014-10-21T15:45:31.343Z
It is indeed correct. Ok
Tayfun Pay
CC BY-SA 3.0
2013-05-17T09:06:49.507Z
2014-10-21T15:49:27.353Z
2014-10-21T15:49:27.353Z
Jan Johannsen
<p>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}$ ?  </p>

CC BY-SA 3.0
2013-05-16T23:55:33.650Z
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...
Joshua Grochow
CC BY-SA 3.0
2013-05-17T16:08:15.017Z
@JoshuaGrochow Thanks! How about if ${\bf P} = {\bf PP}$ but ${\bf P} \neq {PSPACE}$. Can we get another class by Ladner?
Tayfun Pay
CC BY-SA 3.0
2013-05-18T16:09:31.753Z
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$.
Joshua Grochow
<cc.complexity-theory><complexity-classes>
Syntactic Complexity Class ${\bf X}$ such that ${\bf PP} \subseteq {\bf X} \subseteq {\bf PSPACE}$
Tayfun Pay
# Syntactic Complexity Class ${\bf X}$ such that ${\bf PP} \subseteq {\bf X} \subseteq {\bf PSPACE}$

(Asked by: username_0 on 2013-05-16)

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

**Tags:** cc.complexity-theory, complexity-classes

> **Comments:**
> **username_1**: 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...  
> **username_0**: @JoshuaGrochow Thanks! How about if ${\bf P} = {\bf PP}$ but ${\bf P} \neq {PSPACE}$. Can we get another class by Ladner?  
> **username_1**: 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$.  

---

## 1 answers

### Answer by username_2 on 2013-05-17. Score: 14 | Accepted answer

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](http://dx.doi.org/10.1016/0304-3975%2895%2900237-5):
$\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.

> **Comments:**
> **username_0**: I specifically say non-relativized... There is also ${\bf\#P} \cup {\bf \#NP} \cup ... $  
> **username_1**: @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?  
> **username_0**: It is indeed correct. Ok  

---

