patternMinor
Padding in proof of space hierarchy theorems
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.
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))$.
$$ 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.