# Language in $PSPACE$ and not necessarily in $P$ if $P=PP$?

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

• 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. Jun 22, 2019 at 14:47
• I guess you mean besides $PSPACE$-complete languages, which is trivial. Aug 17, 2019 at 12:20

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 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

• Would any of these languages collapse to $PSAPCE$ or to $P$ if $NC=PP$ actually held? How far can we go down below $NC$ and still have proper separation? Jul 24, 2019 at 19:06