1
$\begingroup$

I am reading Arora-Barak's Complexity book. In Chapter 4, they state and prove the following theorem.

enter image description here

Why $S$ should be space constructible? Wouldn't all three containments of theorem hold, even if $S$ is not space constructible?

My other question is about Remark 4.3, the book claims that if $S$ is space constructible then you can make an $NSPACE(S(n))$ machine halt on every sequence of non-deterministic choices by keeping a counter till $2^{O(S(n))}$. I am not sure how we can keep such a counter in $S(n)$ space. The space constructability of $S$ implies that we can compute $S(n)$ in $O(S(n))$ space, not $2^{O(S(n))}$ in $O(S(n))$ space.

$\endgroup$
1
$\begingroup$

To answer your first question, this is tremendously unimportant. You typically don't encounter "funny" functions in actual complexity classes you may encounter in practice. Also, the answer to your question might depend on the exact definitions, which is a sign that you shouldn't be considering these complexity classes in the first place. That said, probably some of these inclusions do hold regardless of space-constructibility.

Regarding the second question, suppose that you computed $S(n)$ (in binary), and are interested to compute $2^{CS(n)}$. First, multiply $S(n)$ by $C$; this uses $O(\log S(n))$ space. Second, count $CS(n)$ spaces, fill them with zeroes, and add a one to the left. You have computed the binary representation of $2^{CS(n)}$, using additional $S(n)+1$ space.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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