In "Computational Complexity: A Modern Approach", it states that to prove that $NSPACE(s(n))\subseteq DTIME(2^{O(s(n)})$, we can do the following:

By enumerating over all possible configurations, we can construct the graph $G_{M,x}$ in $2^{O(s(n)}$ time and check whether $C_{start}$ is connected to $C_{accept}$ in $G_{M,x}$.

As a condition for this proof, the book states that $s$ must be space-constructible. I can't work out exactly how the 'construction' of the configuration graph $G_{M,x}$ takes place, and thus why it requires that $s$ be space-constructible.

Moreover, the book makes the following remark:

Some texts define a nondeterministic space-bounded machine with the adittional restriction that it has to halt and produce an answer on every input regardless of the sequence of nondeterministic choices. However, if we focus on bounds where $s(n)$ is space-constructible, this restriction is unnecessary since the NDTM can be easily modified to always halt [by keeping a counter].

Here, I understand why $s$ needs to be space-constructible. Does this remark relate in any way to the proof above?



Your Answer

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