Sipser first introduces space constructible functions. Then uses the definition to prove the space hierarchy theorem:

if f(n) is a space constructible function then there are languages that can be decided in O(f(n)) space but not in o(f(n)) space.

The author only mentions as most encountered functions are space constructible, it is a good assumption. Are there any cases where non space constructible functions of are interest ? How does the space hierarchy theorem changes under such conditions ?


1 Answer 1


Your question is answered on Wikipedia: for any $s(n)$, and $f(n) = O(s(n))$, and any computable $g(n) = o(s(n))$, $\mathsf{DSPACE}(f(n)) \neq \mathsf{DSPACE}(g(n))$. This is a result due to Geffert.


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.