HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

How to prove SPACE-TMSAT is PSPACE-hard?

Submitted by: @import:stackexchange-cs··
0
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?

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.