patternMinor
How hard are PSPACE-complete problems?
Viewed 0 times
arehardpspacecompletehowproblems
Problem
There are already good answers from several perspectives regarding the "hardness" of $PSPACE$-complete problems, such as this: What is practical difference between NP and PSPACE-complete?
But what are the practical implications when we actually try to solve (decide) a $PSPACE$-complete problem on a deterministic Turing machine? If $PSPACE \neq NP$ (or $PSPACE \neq P$, should it make a difference) then obviously it will take super-polynomial (exponential?) time. But what about space? Is there some $k>1$ that we know of such that it will definitely take $\Omega(n^k)$ space? And do we know for sure that it won't take more than $O(n^l)$ space for some $l$?
(Or is the question itself stated badly for some reason?)
But what are the practical implications when we actually try to solve (decide) a $PSPACE$-complete problem on a deterministic Turing machine? If $PSPACE \neq NP$ (or $PSPACE \neq P$, should it make a difference) then obviously it will take super-polynomial (exponential?) time. But what about space? Is there some $k>1$ that we know of such that it will definitely take $\Omega(n^k)$ space? And do we know for sure that it won't take more than $O(n^l)$ space for some $l$?
(Or is the question itself stated badly for some reason?)
Solution
By definition, PSPACE consists of all languages decided by some Turing machine using polynomial space. So every language in PSPACE can be decided by some Turing machine using space $O(n^\ell)$ for some $\ell$. The space hierarchy theorem ensures moreover that for any $\ell$ there is a language in PSPACE which requires space $\Omega(n^\ell)$.
Any PSPACE-hard language requires space $\Omega(n^k)$ for some $k$, since otherwise any language in PSPACE would be decided by a Turing machine using subpolynomial space, and this contradicts the space hierarchy theorem.
For any $k > 0$ there is a PSPACE-hard language which can be decided in space $O(n^k)$. Indeed, take any PSPACE-complete language $L$. It can be decided using space $O(n^\ell)$ for some $\ell$. Consider now the language $L' = \{(x,0^{|x|^{\ell/k}}) : x \in L\}$, which is PSPACE-hard by reduction from $L$. An algorithm for $L$ can be converted to one for $L'$ which uses $\log n$ space to verify the input structure and $O(|x|^\ell)$ for the rest. Since $n \geq |x|^{\ell/k}$, $O(|x|^\ell) = O(n^{(k/\ell)\ell}) = O(n^k)$.
Any PSPACE-hard language requires space $\Omega(n^k)$ for some $k$, since otherwise any language in PSPACE would be decided by a Turing machine using subpolynomial space, and this contradicts the space hierarchy theorem.
For any $k > 0$ there is a PSPACE-hard language which can be decided in space $O(n^k)$. Indeed, take any PSPACE-complete language $L$. It can be decided using space $O(n^\ell)$ for some $\ell$. Consider now the language $L' = \{(x,0^{|x|^{\ell/k}}) : x \in L\}$, which is PSPACE-hard by reduction from $L$. An algorithm for $L$ can be converted to one for $L'$ which uses $\log n$ space to verify the input structure and $O(|x|^\ell)$ for the rest. Since $n \geq |x|^{\ell/k}$, $O(|x|^\ell) = O(n^{(k/\ell)\ell}) = O(n^k)$.
Context
StackExchange Computer Science Q#70263, answer score: 7
Revisions (0)
No revisions yet.