snippetMinor
How to prove SPACE-TMSAT is PSPACE-hard?
Viewed 0 times
spacehardpspaceprovehowtmsat
Problem
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?
$\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?
Solution
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$.
Context
StackExchange Computer Science Q#106492, answer score: 3
Revisions (0)
No revisions yet.