patternMinor
PSPACE-complete problems can't be in NL using the space hierarchy theorem?
Viewed 0 times
canthespacehierarchypspacecompleteusingtheoremproblems
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#75805, answer score: 5
Revisions (0)
No revisions yet.