Space Hierarchy Theorem - Comparison and Improvements

Comparison and Improvements

The space hierarchy theorem is stronger than the analogous time hierarchy theorems in several ways:

• It only requires s(n) to be at least log n instead of at least n.
• It can separate classes with any asymptotic difference, whereas the time hierarchy theorem requires them to be separated by a logarithmic factor.
• It only requires the function to be space-constructible, not time-constructible.

It seems to be easier to separate classes in space than in time. Indeed, whereas the time hierarchy theorem has seen little remarkable improvement since its inception, the nondeterministic space hierarchy theorem has seen at least one important improvement by Viliam Geffert in his 2003 paper "Space hierarchy theorem revised". This paper made several striking generalizations of the theorem:

• It relaxes the space-constructibility requirement. Instead of merely separating the union classes DSPACE(O(s(n)) and DSPACE(o(s(n)), it separates DSPACE(f(n)) from DSPACE(g(n)) where f(n) is an arbitrary O(s(n)) function and g(n) is a computable o(s(n)) function. These functions need not be space-constructible or even monotone increasing.
• It identifies a unary language, or tally language, which is in one class but not the other. In the original theorem, the separating language was arbitrary.
• It does not require s(n) to be at least log n; it can be any nondeterministically fully space-constructible function.