I understand that the language:

$\operatorname{SPACE-TMSAT} = \{⟨M, w, 1^n⟩ : \text{DTM $M$ accepts $w$ in space $n$}\}$

is in PSPACE since it doesn't use more than $n$ space. But to prove that it is PSPACE-complete, we need to do the reduction from any other PSPACE language to it. If we assume the language to run on a DTM using $O(n^k)$ space, how could we reduce it to SPACE-TMSAT?


1 Answer 1


Suppose $L$ is accepted by some machine $M$ using up to $p(n)$ space, for some polynomial $p(n)$. We map $w$ to $\langle M, w, 1^{p(|w|)} \rangle$.

  • $\begingroup$ thank you! I guess we assume in the definition of SPACE TMSAT, n is the size of the input. $\endgroup$ Commented Apr 4, 2019 at 22:32
  • 1
    $\begingroup$ No, $n$ is completely arbitrary. $\endgroup$ Commented Apr 5, 2019 at 4:03
  • $\begingroup$ So the input is a binary string consisting Turing machine, machine's input, and a number of ones at the end? $\endgroup$ Commented Apr 5, 2019 at 13:39
  • 1
    $\begingroup$ That's just right. $\endgroup$ Commented Apr 5, 2019 at 14:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.