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

Padding in proof of space hierarchy theorems

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
paddingtheoremsspacehierarchyproof

Problem

Referring to the Wikipedia proof :

Wikipedia proves the space hierarchy theorem using the following language:
$$ L = \{ (\langle M \rangle, 10^k) : \text{$M$ does not accept $(\langle M \rangle, 10^k)$ using space $f(|(\langle M \rangle, 10^k)|)$} \}. $$

Why do we need the padding with $10^k$? How does it help us in the proof, and where does it fail if we do not consider it?

I assume that the same reasoning would be valid also for the nondeterministic version.

Solution

Suppose that we consider instead the language
$$ L = \{ \langle M \rangle : \text{$M$ does not accept $\langle M \rangle$ in space $f(\langle M \rangle)$} \}. $$
We want to show that $L \notin \mathsf{SPACE}(o(f(n))$, that is, that if $M$ uses space $o(f(n))$ then $L(M) \neq L$. This should be the case since $$\langle M \rangle \in L \Leftrightarrow \langle M \rangle \notin L(M).$$
But is this really true? According to the definition of $L$, $\langle M \rangle \in L$ iff $M$ does not accept $\langle M \rangle$ in space $f(\langle M \rangle)$. It could be that $\langle M \rangle \in L$ and $M$ accepts $\langle M \rangle$ using more than $f(\langle M \rangle)$ space. The latter could actually happen, since we are only guaranteed that $M$ uses space $g(n)$ for some function $g(n) = o(f(n))$, which does not preclude $g(|\langle M \rangle|) > f(|\langle M \rangle|)$ at the particular value $|\langle M \rangle|$.

Adding the padding fixes this issue: it cannot be that $g(|(\langle M \rangle, 10^k)|) > f(|(\langle M \rangle, 10^k)|)$ for all $k$, since this would contradict $g(n) = o(f(n))$.

Context

StackExchange Computer Science Q#142761, answer score: 3

Revisions (0)

No revisions yet.