2
$\begingroup$

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?)

$\endgroup$
6
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ Regarding the "$l$", I meant if there is a fixed $l$ which no PSPACE-complete problem is above. But is that true - are there really PSPACE-complete problems in $DSPACE(n)$? How can that be? (I know, this kind of question makes no sense, but it just seems so very unintuitive!) $\endgroup$ – Duke Feb 13 '17 at 20:21
  • 1
    $\begingroup$ My answer proves that there is a PSPACE-complete problem in $\mathsf{DSPACE}(n)$, or even in $\mathsf{DSPACE}(n^{0.1})$, for that matter. Regarding your second question, the space hierarchy theorem shows that no fixed $l$ works. $\endgroup$ – Yuval Filmus Feb 13 '17 at 20:24
  • $\begingroup$ Yeah, I got your proof - more or less... It's just so unintuitive, it contradicts my sense of hardness of PSPACE-complete problems. Anyway, this is such a great answer!! Thanks a lot - I'd very much like to vote you up, but my reputation is too low. Sorry! $\endgroup$ – Duke Feb 13 '17 at 20:29
  • 1
    $\begingroup$ Note that your "requires space $\Omega(n^k)$" requires either the weak definition of $\Omega$ or considering the bit-padded versions, since there are PSPACE-complete languages which are trivial on all even input lengths. ​ ​ $\endgroup$ – user12859 Feb 13 '17 at 21:19

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.