I want to prove that no PSPACE-complete problem is in NL using the space hierarchy theorem. What I want to say is this : From the time hierarchy theorem I know that for every $t(n)$ there exists a language that is decidable in $O(t(n))$ space but not in $o(t(n))$ space. Then I want to assume that there exists $A \in PSPACE\text{-complete} \land A \in NL$ and take a language $L$ that is decidable in $O(n)$ time but not $o(n)$ time, reduce it to $A$, reduce it to $PATH$ and get that through that reduction $L$ is decidable in $\Theta (log(n)^2)$ time, a contradiction.

However my reasoning fails in that the reduction from $L$ to $A$ isn't necessarily a log-space reduction. What am I missing? How do I overcome this?


Use Savitch's theorem, which shows that PSPACE=NPSPACE, and the non-deterministic space hierarchy theorem.

Alternative (suggested by OP): use Savitch's theorem to show that $\mathsf{NL} \subseteq \mathsf{SPACE}(\log^2 n)$, and then the deterministic space hierarchy theorem.

  • $\begingroup$ Would it be possible to use Savitch's theorem that shows that $NL = Space(log^2n)$? I then get that $NL \subset PSPACE$, and then I can say that "the hardest problems in PSPACE must therefore not be in NL", but is there a more formal way to say this? $\endgroup$ – user72505 May 24 '17 at 21:35
  • $\begingroup$ Yes, in this alternative you use Savitch's theorem on NL and then the deterministic space hierarchy theorem. $\endgroup$ – Yuval Filmus May 24 '17 at 21:36
  • $\begingroup$ But still, how do I formally prove that any problem that is PSPACE complete can't be in NL? Is there a way to say that since NL is a strict subset of PSPACE, the hardest problems of PSPACE (those that are PSPACE complete, for example) can't possibly be in NL? $\endgroup$ – user72505 May 24 '17 at 21:38
  • $\begingroup$ You use the space hierarchy theorem together with the definition of PSPACE-completeness. I'm afraid you'll have to work it out on your own. $\endgroup$ – Yuval Filmus May 24 '17 at 21:40
  • $\begingroup$ This doesn't seem to work, no way to get around the difference between completeness for polytime reductions and logspace reductions. $\endgroup$ – Ariel May 25 '17 at 18:38

This question is currently open, since a positive answer (i.e. no complete problems for PSPACE can lie in NL) would imply $\mathsf{P}\neq\mathsf{PSPACE}$. This statement is actually equivalent to $\mathsf{P}\neq\mathsf{PSPACE}$ (as a PSPACE complete problem in NL obviously implies P=PSPACE).

Examine the equivalent statement, that $\mathsf{P}=\mathsf{PSPACE}$ implies there exists a PSPACE complete problem in NL. To see why this holds, note that if $\mathsf{P}=\mathsf{PSPACE}$ then every non trivial language $L\in\mathsf{PSPACE}$ (i.e. $L\neq \emptyset,\Sigma^*$) is complete for PSPACE. Now let $L$ be some non trivial language in NL (which is a subset of PSPACE), then $L$ is a PSPACE complete problem which lies in NL.


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.