patternMinor
Proof of Space Hierarchy Theorem incompatible with Linear Speed Up Theorem for time
Viewed 0 times
linearspacehierarchywithtimetheoremspeedforincompatibleproof
Problem
In this proof of the Space Hierarchy Theorem the following language is defined
$$
L = \{ (\langle M \rangle, 10^k) : M \mbox{ does not accept } (\langle M \rangle, 10^k) \mbox{ using space } \le f(|\langle M \rangle, 10^k|) \}.
$$
And then stated:
Now, for any machine $M$ that decides a language in space $o(f(n))$, $L$ will differ in at least one spot from the language of $M$. Namely, for some large enough $k$, $M$ will use space $\le f(|\langle M \rangle|, 10^k|)$
on $(\langle M \rangle, 10^k)$ and will therefore differ at its value.
I get the diagonalization argument, but what makes me wonder according to the linear speed up theorem for space we have [see for example Hopcroft/Ullman, 71]:
If $L$ is accepted by an $S(n)$ space-bounded Turing machine with $k$ storage tapes, then for any $c > 0$, $L$ is accepted by a $cS(n)$ space-bounded Turing machine.
As shown in the linked wikipedia article $L$ is accepted by a Turing machine using $f(n)$-bounded space, then by linear speed up $L$ is also accepted by some machine $M'$ using at most $\frac{f(n)}{2}$ tape cells. But then we get a contradiction on the inputs $(\langle M' \rangle, 10^k)$, as $M'$ accepts $L$ if $(\langle M' \rangle, 10^k)$ is accepted, then $(\langle M' \rangle, 10^k) \notin L$, contradiction, and similar for the case if it is not accepted. If $(\langle M' \rangle, 10^k)$ is not accepted by $M'$ then $(\langle M' \rangle, 10^k) \in L$ by definition of $L$, but $(\langle M' \rangle, 10^k) \notin L(M') = L$, a contradiction.
My reasoning seems to be fine, but it should not be... what am I missing here? In my argument, the problem is with the speed up and essentially it derives that if speed up is possible, then we can separate $f$ and $cf$ for $0 < c < 1$, i.e., speed up is not possible. The only valid conclusion would be that linear speed up is not possible, but that is certainly not true...
$$
L = \{ (\langle M \rangle, 10^k) : M \mbox{ does not accept } (\langle M \rangle, 10^k) \mbox{ using space } \le f(|\langle M \rangle, 10^k|) \}.
$$
And then stated:
Now, for any machine $M$ that decides a language in space $o(f(n))$, $L$ will differ in at least one spot from the language of $M$. Namely, for some large enough $k$, $M$ will use space $\le f(|\langle M \rangle|, 10^k|)$
on $(\langle M \rangle, 10^k)$ and will therefore differ at its value.
I get the diagonalization argument, but what makes me wonder according to the linear speed up theorem for space we have [see for example Hopcroft/Ullman, 71]:
If $L$ is accepted by an $S(n)$ space-bounded Turing machine with $k$ storage tapes, then for any $c > 0$, $L$ is accepted by a $cS(n)$ space-bounded Turing machine.
As shown in the linked wikipedia article $L$ is accepted by a Turing machine using $f(n)$-bounded space, then by linear speed up $L$ is also accepted by some machine $M'$ using at most $\frac{f(n)}{2}$ tape cells. But then we get a contradiction on the inputs $(\langle M' \rangle, 10^k)$, as $M'$ accepts $L$ if $(\langle M' \rangle, 10^k)$ is accepted, then $(\langle M' \rangle, 10^k) \notin L$, contradiction, and similar for the case if it is not accepted. If $(\langle M' \rangle, 10^k)$ is not accepted by $M'$ then $(\langle M' \rangle, 10^k) \in L$ by definition of $L$, but $(\langle M' \rangle, 10^k) \notin L(M') = L$, a contradiction.
My reasoning seems to be fine, but it should not be... what am I missing here? In my argument, the problem is with the speed up and essentially it derives that if speed up is possible, then we can separate $f$ and $cf$ for $0 < c < 1$, i.e., speed up is not possible. The only valid conclusion would be that linear speed up is not possible, but that is certainly not true...
Solution
The Wikipedia proof is bogus.
As you have proven, the description for $L$ is incomplete. It should read:
$$
L = \{ (\langle M \rangle, 10^k) : M \mbox{ does not accept } x = (\langle M \rangle, 10^k) \mbox{ using space } \le f(|x|)
\; \textbf{and time} \; \le 2^{f(|x|)} \}
$$
This corrects the proof because now $M$ (or $M'$) can still accept $x = (\langle M \rangle, 10^k)$ and take space $\le f(|x|)$. Actually, $(\langle M \rangle, 10^k) \in L$ has a quite reasonable explanation in that $M$ attempts to simulate $M$, which (as a subroutine) attempts to simulate $M$ again, and so forth and so on, until eventually $2^{f(|x|)}$ steps elapse and the whole procedure is interrupted. Hence, $M$ does not accept $x$ using space $\le f(|x|)$ and time $\le 2^{f(|x|)}$, although it does accept it taking space $\le f(|x|)$ (well, perhaps actually $O(f(|x|))$) and time $> 2^{f(|x|)}$.
As a matter of fact, the purported algorithm for $L$ in the article explicitly states it runs its simulation with a $2^{f(|x|)}$ stopwatch. This is precisely the detail that is missing from the definition of $L$.
As you have proven, the description for $L$ is incomplete. It should read:
$$
L = \{ (\langle M \rangle, 10^k) : M \mbox{ does not accept } x = (\langle M \rangle, 10^k) \mbox{ using space } \le f(|x|)
\; \textbf{and time} \; \le 2^{f(|x|)} \}
$$
This corrects the proof because now $M$ (or $M'$) can still accept $x = (\langle M \rangle, 10^k)$ and take space $\le f(|x|)$. Actually, $(\langle M \rangle, 10^k) \in L$ has a quite reasonable explanation in that $M$ attempts to simulate $M$, which (as a subroutine) attempts to simulate $M$ again, and so forth and so on, until eventually $2^{f(|x|)}$ steps elapse and the whole procedure is interrupted. Hence, $M$ does not accept $x$ using space $\le f(|x|)$ and time $\le 2^{f(|x|)}$, although it does accept it taking space $\le f(|x|)$ (well, perhaps actually $O(f(|x|))$) and time $> 2^{f(|x|)}$.
As a matter of fact, the purported algorithm for $L$ in the article explicitly states it runs its simulation with a $2^{f(|x|)}$ stopwatch. This is precisely the detail that is missing from the definition of $L$.
Context
StackExchange Computer Science Q#104982, answer score: 5
Revisions (0)
No revisions yet.