# PSPACE-complete problems can't be in NL using the space hierarchy theorem?

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.

• 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? – user72505 May 24 '17 at 21:35
• Yes, in this alternative you use Savitch's theorem on NL and then the deterministic space hierarchy theorem. – Yuval Filmus May 24 '17 at 21:36
• 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? – user72505 May 24 '17 at 21:38
• 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. – Yuval Filmus May 24 '17 at 21:40
• This doesn't seem to work, no way to get around the difference between completeness for polytime reductions and logspace reductions. – 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.