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$
$\endgroup$
11
-
$\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$– ArielAug 12, 2020 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$– rus9384Aug 12, 2020 at 17:53
-
$\begingroup$ Not all undecidable languages are NP-hard. See this answer by Yuval. $\endgroup$– ArielAug 12, 2020 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$– ArielAug 12, 2020 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$– rus9384Aug 12, 2020 at 18:15
|
Show 6 more comments
1 Answer
$\begingroup$
$\endgroup$
0
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$.
