Space bounded computations: Review and new separation results. (English) Zbl 0745.68051

Summary: We review the key results about space bounded complexity classes, discuss the central open problems and outline the prominent proof techniques. We show that, for a slightly modified Turing machine model, low level deterministic and nondeterministic space bounded complexity classes are different. Furthermore, for this computation model, we show that Savitch’s theorem and the Immerman-Szelepcsényi theorem do not hold in the range \(\lg \lg n\) to \(\lg n\). We also present other changes in the computation model which bring out and clarify the importance of space constructibility. We conclude by enumerating open problems which arise out of the discussion.


68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
Full Text: DOI


[1] Baker, T.; Gill, J.; Solovay, R., Relativizations of the P = ?NP question, SIAM J. Comput., 4, 4, 431-442 (1975) · Zbl 0323.68033
[2] Freedman, A. R.; Ladner, R. E., Space bounds for processing counterless inputs, J. Comput. System Sci., 11, 118-128 (1975) · Zbl 0307.68036
[3] Freivalds, R., On the worktime of deterministic and non-deterministic turing machines, Latvijskij Matematiceskij Eshegodnik, 23, 158-165 (1979) · Zbl 0462.68028
[4] V. Geffert, Nondeterministic computations in sublogarithmic space and space constructibility ICALP ’90; V. Geffert, Nondeterministic computations in sublogarithmic space and space constructibility ICALP ’90 · Zbl 0765.68035
[5] Hartmanis, J.; Chang, R.; Kadin, J.; Mitchell, S., Some observations about space bounded computations, Bull. EATCS, 35, 82-92 (1988) · Zbl 0667.68062
[6] Hartmanis, J.; Hunt, H. H., On the LBA problem and its importance in the theory of computation, SIAM-AMS, 7, 1-26 (1974) · Zbl 0301.68056
[7] Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701
[8] Immerman, N., Nondeterministic space is closed under complement, (Proc. Structure in Complexity Theory Third Annu. Conf. (1988), Computer Society of IEEE), 112-115
[9] Kannan, R., Alternation and the power of nondeterminism, ACM Symp. on Theory of Computing, 344-346 (1983)
[10] Kuroda, S. Y., Classes of languages and linearly-bounded automata, Inform. and Control, 7, 207-223 (1964) · Zbl 0199.04002
[11] Lewis, P. M.; Stearns, R. E.; Hartmanis, J., Memory bounds for recognition of context-free and context-sensitive languages, IEEE Conf. Record on Switching Circuit Theory and Logic Design, 191-202 (1965) · Zbl 0272.68054
[12] Savitch, W. J., Relationships between nondeterministic and deterministic tape complexities, J. Comput. System Sci., 4, 177-192 (1970) · Zbl 0188.33502
[13] Seiferas, J., A note on notions of tape constructibility, (Technical Report CSD-TR 187 (1976), Pennsylvania State University)
[14] Sipser, M., Halting space-bounded computations, Theoret. Comput. Sci., 10, 335-338 (1980) · Zbl 0423.68011
[15] Stearns, R. E.; Hartmanis, J.; Lewis, P. M., Hierarchies of memory limited computations, 1965 IEEE Conf. Record on Switching Circuit Theory and Logical Design, 179-190 (1965) · Zbl 0229.02033
[16] Szelepcsényi, R., The method of forcing for nondeterministic automata, Bull. EATCS, 33, 96-100 (1987) · Zbl 0664.68082
[17] Szepietowski, A., Some notes on strong and weak log log \(n\) space complexity (1988), Mathematical Department, Technical University of Gdańsk: Mathematical Department, Technical University of Gdańsk Poland, Majakowskiego 11/12, PL-80-952, Gdańsk
[18] Szepietowski, A., If deterministic and nondeterministic space complexity are equal for log log \(n\) then they are equal for log \(n\), (STACS ’89. STACS ’89, Lecture Notes in Computer Science, 349 (1989), Springer: Springer Berlin), 251-255 · Zbl 0701.68033
[19] Wilson, C. B., Relativized circuit complexity, J. Comput. System Sci, 31, 169-181 (1985) · Zbl 0583.68023
[20] Wilson, C. B., Parallel computation and the NC hierarchy relativized, (Structure in Complexity Theory. Structure in Complexity Theory, Lecture Notes in Computer Science, 223 (1986), Springer: Springer Berlin), 362-382 · Zbl 0615.68039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.