Abstract
We show that, for an arbitrary function h(n) and each recursive function ℓ(n), that are separated by a nondeterministically fully space constructible g(n), such that h(n)∈Ω(g(n)) but ℓ(n)∉Ω(g(n)), there exists a unary language \( \mathcal{L} \) in NSPACE(h(n)) - NSPACE(ℓ(n)). The same holds for the deterministic case.
The main contribution to the well-known Space Hierarchy Theorem is that (i) the language \( \mathcal{L} \) separating the two space classes is unary (tally), (ii) the hierarchy is independent of whether h(n) or ℓ(n) are in Ω(log n) or in o(log n), (iii) the functions h(n) or ℓ(n) themselves need not be space constructible nor monotone increasing. This allows us, using diagonalization, to present unary languages in such complexity classes as, for example, NSPACE(log log n·log*n) - NSPACE(log log n).
This work was supported by the Slovak Grant Agency for Science (VEGA) under contract #1/7465/20 “Combinatorial Structures and Complexity of Algorithms.”
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Braunmühl, B. von, Gengler, R., Rettinger, R.: The alternation hierarchy for sublogarithmic space is infinite. Comput. Complexity 3 (1993) 207–30.
Fischer, M., Meyer, A., Seiferas, J.: Separating nondeterministic time complexity classes. J. Assoc. Comput. Mach. 25 (1978) 146–67.
Freedman, A.R., Ladner, R. E.: Space bounds for processing contentless inputs. J. Comput. System Sci. 11 (1975) 118–28.
Geffert, V.: Nondeterministic computations in sublogarithmic space and space constructibility. SIAM J. Comput. 20 (1991) 484–98.
Geffert, V.: Tally versions of the Savitch and Immerman-Szelepcsényi theorems for sublogarithmic space. SIAM J. Comput. 22 (1993) 102–13.
Geffert, V.: A hierarchy that does not collapse: Alternations in low level space. RAIRO Inform. Théor. 28 (1994) 465–512.
Geffert, V.: Bridging across the log(n) space frontier. Inform. & Comput. 142 (1998) 127–58.
Hartmanis, J., Lewis II, P. M., Stearns, R. E.: Hierarchies of memory limited computations. In IEEE Conf. Record on Switching Circuit Theory and Logical Design (1965) 179–90.
Hopcroft, J. E., Ullman, J.D.: Some results on tape-bounded Turing machines. J. Assoc. Comput. Mach. 16 (1969) 168–77.
Ibarra, O. H.: A note concerning nondeterministic tape complexities. J. Assoc. Comput. Mach. 19 (1972) 608–12.
Immerman, N.: Nondeterministic space is closed under complementation. SIAM J. Comput. 17 (1988) 935–38.
Liśkiewicz, M., Reischuk, R.: The sublogarithmic alternating space world. SIAM J. Comput. 25 (1996) 828–61.
Savitch, W. J.: Relationships between nondeterministic and deterministic tape complexities. J. Comput. System Sci. 4 (1970) 177–92.
Sipser, M.: Halting space bounded computations. Theoret. Comput. Sci. 10 (1980) 335–38.
Szelepcsényi, R.: The method of forced enumeration for nondeterministic automata. Acta Inform. 26 (1988) 279–84.
Szepietowski, A.: Turing Machines with Sublogarithmic Space. Springer-Verlag, Lect. Notes Comput. Sci. 843 (1994).
Žák, S.: A Turing machine time hierarchy. Theoret. Comput. Sci. 26 (1983) 327–33.
Žák, S.: A sharp separation below log(n). Tech. Rep. 655/1995, Inst. Comput. Sci., Czech Academy of Sciences (1995).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Geffert, V. (2001). Space Hierarchy Theorem Revised. In: Sgall, J., Pultr, A., Kolman, P. (eds) Mathematical Foundations of Computer Science 2001. MFCS 2001. Lecture Notes in Computer Science, vol 2136. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44683-4_34
Download citation
DOI: https://doi.org/10.1007/3-540-44683-4_34
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42496-3
Online ISBN: 978-3-540-44683-5
eBook Packages: Springer Book Archive