0
$\begingroup$

I have read and understood various proofs, but have not been able to understand precisely why we require $S=\Omega(\log n)$.

$\endgroup$

1 Answer 1

0
$\begingroup$

We believe that $DSPACE(X) \subseteq DTIME(X)$ is false. As a consequence, $X$ must be chosen so that $X \neq 2^{O(X)}$. Additionally, considering $DSPACE(X) \subseteq DTIME(Y)$ we want $ Y = 2^{O(X)}$ to allow the Turing machine requiring $X$ space to halt on all of its inputs: this is because the number of configurations is $O(2^{O(X)})$ and any accepting computation must halt within $O(2^{O(X)})$ steps, i.e. this is $2^{O(X)}$ if $X = \Omega(\lg n)$. Moreover, the function $X$ must be space constructible as well, and $\lg n$ is space constructible. This is also consistent with the definition of the complexity classes $L$ and $P$. The former is the class of the languages (or problems) requiring at most $O(\lg n)$ space, the latter the class of languages requiring at most polynomial time. The relationship $L \subset P$ holds because a Turing machine requiring at most logarithmic space can use at most linear time, so polynomial time.

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