<p>Trivially there will be space-bounded classes <span class="math-container">$P\ne Space(n)\subsetneq Space(n^2)\subsetneq PSPACE$</span>, and <span class="math-container">$NSpace(n)\subsetneq NSpace(n^2)\subsetneq PSPACE$</span>, which do not collapse due to the space hierarchy theorem.</p>
<p>More interestingly, the <a href="https://www.math.ucdavis.edu/%7Egreg/zoology/diagram.xml" rel="nofollow noreferrer">Complexity Zoo</a> lists two other classes that is in PSPACE but not in CH, namely</p>
<ul>
<li><span class="math-container">$QSZK$</span> (Quantum Statistical Zero Knowledge)</li>
<li><span class="math-container">$RG[\#1]$</span> (single-round referreed games).</li>
</ul>
<p>Perhaps <span class="math-container">$QSZK$</span> satisfies your condition. The best published upper bound (that I can find) is that <span class="math-container">$QSZK\subseteq PSPACE$</span> by Watrous[1]. Perhaps it does not satisfy your condition; because it has a complete problem that asks to determine the trace distance between the quantum states produced by two quantum circuits given as input, and this is typically doable in <span class="math-container">$P^{\#P}$</span>, which you have assumed is equal to <span class="math-container">$P^{\#P}=P$</span>. I don't know, and invite people to think about whether <span class="math-container">$QSZK\subseteq CH$</span> or not. Since you asked specifically for a hierarchy, you can think about the hierarchy <span class="math-container">$QSZK^{{QSZK}^{\cdots}}$</span>. It is unknown whether this class is self-low, i.e. whether <span class="math-container">$QSZK=QSZK^{QSZK}$</span> and the hierarchy collapses.</p>
<p><strong>Update</strong></p>
<p>Known results:</p>
<p><span class="math-container">$$QMA=QIP[1]\subseteq A_0PP\subseteq PP$$</span>
<span class="math-container">$$QMA[2]=QMA[k]$$</span>
<span class="math-container">$$QSZK\subseteq QIP[2]\subseteq QIP[3]=QIP=PSPACE.$$</span></p>
<p>Perhaps <span class="math-container">$RG[\#1]$</span> satisfies your condition. No upper bound is known except that <span class="math-container">$RG[\#1]\subseteq RG[\#2]=PSPACE\subseteq RG=EXP$</span>.</p>
<p>[1] J. Watrous. Limits on the power of quantum statistical zero-knowledge, to appear in Proceedings of IEEE FOCS'2002</p>

CC BY-SA 4.0
2019-06-22T14:43:40.170Z
2021-02-20T15:39:32.913Z
2021-02-20T15:39:32.913Z
Lieuwe Vinkhuijzen
<p>If <span class="math-container">$P=PP$</span> then the counting hierarchy collapses to <span class="math-container">$CH=P$</span>. Because so many complexity classes are contained in <span class="math-container">$CH$</span>, this causes most classes to now be contained in <span class="math-container">$P$</span>. My question is whether this is true for all languages in <span class="math-container">$PSPACE$</span>, or not.</p>

<blockquote>
  <p>What is a candidate language <span class="math-container">$L\in PSPACE$</span> such that we do not know that <span class="math-container">$P=PP$</span> implies that <span class="math-container">$L\in P$</span>?</p>
</blockquote>

CC BY-SA 4.0
2019-08-17T12:20:19.613Z
I guess you mean besides $PSPACE$-complete languages, which is trivial.
rus9384
CC BY-SA 4.0
2019-06-22T14:47:37.213Z
Please explain when you downvote. Note that Turbo is not asking about proven separations, but rather about candidate classes that resist collapse even when $P=CH$, if I understand correctly, which is a good question imo.
Lieuwe Vinkhuijzen
<cc.complexity-theory><complexity-classes><counting-complexity>
Language in $PSPACE$ and not necessarily in $P$ if $P=PP$?
Turbo
# Language in $PSPACE$ and not necessarily in $P$ if $P=PP$?

(Asked by: username_0 on 2019-06-22)

If $P=PP$ then the counting hierarchy collapses to $CH=P$. Because so many complexity classes are contained in $CH$, this causes most classes to now be contained in $P$. My question is whether this is true for all languages in $PSPACE$, or not.

> What is a candidate language $L\in PSPACE$ such that we do not know that $P=PP$ implies that $L\in P$?

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

> **Comments:**
> **username_2**: Please explain when you downvote. Note that username_0 is not asking about proven separations, but rather about candidate classes that resist collapse even when $P=CH$, if I understand correctly, which is a good question imo.  
> **username_1**: I guess you mean besides $PSPACE$-complete languages, which is trivial.  

---

## 1 answers

### Answer by username_2 on 2019-06-22. Score: 5 | Accepted answer

Trivially there will be space-bounded classes $P\ne Space(n)\subsetneq Space(n^2)\subsetneq PSPACE$, and $NSpace(n)\subsetneq NSpace(n^2)\subsetneq PSPACE$, which do not collapse due to the space hierarchy theorem.

More interestingly, the [Complexity Zoo](https://www.math.ucdavis.edu/%7Egreg/zoology/diagram.xml) lists two other classes that is in PSPACE but not in CH, namely

* $QSZK$ (Quantum Statistical Zero Knowledge)
* $RG[\#1]$ (single-round referreed games).

Perhaps $QSZK$ satisfies your condition. The best published upper bound (that I can find) is that $QSZK\subseteq PSPACE$ by Watrous[1]. Perhaps it does not satisfy your condition; because it has a complete problem that asks to determine the trace distance between the quantum states produced by two quantum circuits given as input, and this is typically doable in $P^{\#P}$, which you have assumed is equal to $P^{\#P}=P$. I don't know, and invite people to think about whether $QSZK\subseteq CH$ or not. Since you asked specifically for a hierarchy, you can think about the hierarchy $QSZK^{{QSZK}^{\cdots}}$. It is unknown whether this class is self-low, i.e. whether $QSZK=QSZK^{QSZK}$ and the hierarchy collapses.

**Update**

Known results:

$$QMA=QIP[1]\subseteq A\_0PP\subseteq PP$$
$$QMA[2]=QMA[k]$$
$$QSZK\subseteq QIP[2]\subseteq QIP[3]=QIP=PSPACE.$$

Perhaps $RG[\#1]$ satisfies your condition. No upper bound is known except that $RG[\#1]\subseteq RG[\#2]=PSPACE\subseteq RG=EXP$.

[1] J. Watrous. Limits on the power of quantum statistical zero-knowledge, to appear in Proceedings of IEEE FOCS'2002


---

