patternMinor
How is the space hierarchy theorem different for non space constructible functions?
Viewed 0 times
thespacenonhierarchyconstructibledifferenttheoremforhowfunctions
Problem
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 ?
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 ?
Solution
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.
Context
StackExchange Computer Science Q#52897, answer score: 4
Revisions (0)
No revisions yet.