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

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

• I'm pretty sure Mahaney's theorem remains true even if we require that the sparse language is NP-hard (i.e. not necessarily in NP), so you still get $P=NP$, and combining with my answer $P=PSPACE$. Aug 12, 2020 at 17:49
• @Ariel, I am not sure on the upper limits of the sparse language required by Mahaney's theorem. There are undecidable sparse languages, and since they are least as hard as $\mathsf{NP}$-complete languages, that would make $\mathsf{P = NP}$. But since $\mathsf{P}$ vs. $\mathsf{NP}$ still is an open problem I don't think that's a correct way. Aug 12, 2020 at 17:53
• Not all undecidable languages are NP-hard. See this answer by Yuval. Aug 12, 2020 at 17:53
• Go over the proof of Mahaney's carefully, the sparse language is only used to prune possible assignments during the search of a satisfying one. We need sparsity to keep the number of possible partial assignments small, but we never actually care about membership to the sparse language. Aug 12, 2020 at 17:57
• @Ariel, so, I guess all known sparse languages are $\mathsf{NP}$-intermediate problems and intermediate problems for weaker (classes) or their $/poly$ and $/log$ counterparts. Aug 12, 2020 at 18:15

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