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

  • $\begingroup$ 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$. $\endgroup$ – Ariel Aug 12 at 17:49
  • $\begingroup$ @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. $\endgroup$ – rus9384 Aug 12 at 17:53
  • $\begingroup$ Not all undecidable languages are NP-hard. See this answer by Yuval. $\endgroup$ – Ariel Aug 12 at 17:53
  • $\begingroup$ 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. $\endgroup$ – Ariel Aug 12 at 17:57
  • $\begingroup$ @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. $\endgroup$ – rus9384 Aug 12 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$.

| cite | improve this answer | |

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.