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

Question

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?

Answer 1

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.

Answer 2

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.