0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Lieuwe Vinkhuijzen Jun 22 at 14:47
  • $\begingroup$ I guess you mean besides $PSPACE$-complete languages, which is trivial. $\endgroup$ – rus9384 Aug 17 at 12:20
5
$\begingroup$

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.

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – T.... Jul 24 at 19:06

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.