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

1 Answer 1

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.

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.