3
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ thank you! I guess we assume in the definition of SPACE TMSAT, n is the size of the input. $\endgroup$ – Hadi GhahremanNezhad Apr 4 at 22:32
  • 1
    $\begingroup$ No, $n$ is completely arbitrary. $\endgroup$ – Yuval Filmus Apr 5 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$ – Hadi GhahremanNezhad Apr 5 at 13:39
  • 1
    $\begingroup$ That's just right. $\endgroup$ – Yuval Filmus Apr 5 at 14:00

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.