Editing Space hierarchy theorem (section)

== Comparison and improvements ==

The space hierarchy theorem is stronger than the analogous [[time hierarchy theorem]]s 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 only requires <math>f(n)</math> to be space-constructible, with no constraint on the constructability of <math>g(n)</math>.
* However, it is known from results in axiomatic complexity theory that the theorem is false if <math>f(n)</math> is not required to be space-constructible.<ref name=":1">{{Cite book |last1=Balcázar |first1=José Luis |title=Structural Complexity I |last2=Díaz |first2=Josep |last3=Gabarró |first3=Joaquim |publisher=Springer-Verlag |year=1988 |isbn=3-540-18622-0}}</ref>{{Pg|page=55}}

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 generalizations of the theorem:

* It relaxes the space-constructibility requirement. Let <math>s</math> be a nondeterministically fully space-constructible function. Let {{tmath|f(n)}} be an arbitrary {{tmath|\Omega(s(n))}} function, and <math>g(n)</math> be a [[computable function|computable]] {{tmath|o(s(n))}} function. These functions need not be space-constructible or even monotone increasing. Then {{tmath|\mathsf{DSPACE}(f(n)) \subsetneq \mathsf{DSPACE}(g(n)) }} and {{tmath|\mathsf{NSPACE}(f(n)) \subsetneq \mathsf{NSPACE}(g(n)) }}.
* 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 {{tmath|s(n)}} to be at least log ''n''; it can be any nondeterministically fully space-constructible function.