Is there any consequence to the existence of $\mathsf{PSPACE}$-complete sparse language like with Mahaney's theorem?

cs.stackexchange https://cs.stackexchange.com/questions/129210

Question

Mahaney's theorem states that the existence of $\mathsf{NP}$-complete sparse language would lead to $\mathsf{P = NP}$. Is there any result result regarding the same for the complexity class $\mathsf{PSPACE}$, like "if there is a $\mathsf{PSPACE}$-complete sparse language, $\mathsf{PP = PSPACE}$" or the same for any other complexity class within $\mathsf{PSPACE}$?

Was it helpful?

Solution

A quick result is that $PSPACE=\Sigma_2$.

First show that $PSPACE\subseteq P/Poly$, and as a result $PSPACE\subseteq \Sigma_2$ (If finding an entry of a computation table is in P/Poly, then it is also in $\Sigma_2$, since we can guess a circuit and locally verify its correctness as described here).

To see why having a PSPACE-complete sparse language $S$ puts PSPACE in P/poly, given $L\in PSPACE$, let $f$ be a reduction from $L$ to $S$. Note that if $|f(x)|$ depends only on $|x|$, then $L\in P/Poly$ since we can concatenate the circuits for $f$ and for $S$ (which is in P/Poly due to being sparse). To overcome the fact that $f$ might vary in the output's length for same input size, note that on length $n$ inputs $f$ can produce output of length $\le n^c$, so given $x$ we can take as a hint all $|x|^c$ circuits for $S$ on input sizes $0,1,...,|x|^c$. Among these circuits, we have the "right" circuit which is able to determine the membership of $f(x)$ to $S$.

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top