3
$\begingroup$

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.

$\endgroup$
2

1 Answer 1

3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.