Abstract
In automata-based complexity one specifies a model of computation and dynamic measures of computational complexity. Once these are defined there are three themes which usually are developed: (i) the existence of hierarchies of complexity classes as determined by hierarchies of bounds on the measures; (ii) trade-offs between the different measures so defined; and (iii) the investigation of the possible extra costs involved when using the deterministic mode of operation as opposed to using the nondeterministic mode of operation. In this paper we are concerned with complexity classes of sets recognized by multitape Turing machines which operate within subelementary time bounds and space bounds. We investigate the structure of these classes in order to learn more about the trade-offs between time and space and about the cost of deterministic simulation of nondeterministic processes.
This research was supported in part by the National Science Foundation under Grant GJ — 30409.
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
Aanderaa, S., On k-tape versus (k+1)-tape real-time computation, to appear.
Book, R., On languages accepted in polynomial time, SIAM J. Computing 1 (1972), 281–287.
Book, R., Comparing complexity classes, J. Computer System Sci., to appear.
Book, R., Translational lemmas, polynomial time, and (lg n)j-space, submitted for publication.
Cook, S., Characterizations of pushdown machines in terms of time-bounded computers, JACM 18 (1971), 4–18.
Cook, S., A hierarchy for nondeterministic time complexity, J. Computer System Sci. 7 (1973), 343–353.
Greibach, S., The hardest context-free language, SIAM J. Computing 2 (1973), 304–310.
Hartmanis, J., H. Hunt, The LBA problem and its importance in the theory of computing, Cornell University Technical Report.
Ibarra, O., A note concerning nondeterministic tape complexities, JACM 19 (1972), 608–612.
Ruby, S., P.C. Fischer, Translational methods and computational complexity, Conf. Record IEEE Sixth Annual Symp. on Switching Circuit Theory and Logical Design (1965), 173–178.
Savitch, W., Relationships between nondeterministic and deterministic tape complexities, J. Computer System Sci. 4 (1970), 177–192.
Book, R., Tally languages and complexity classes, Information and Control, to appear.
Savitch, W., A note on multihead automata and context-sensitive languages, ACTA Informatica 2 (1973), 249–252.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1974 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Book, R.V. (1974). On The Structure of Complexity Classes. In: Loeckx, J. (eds) Automata, Languages and Programming. ICALP 1974. Lecture Notes in Computer Science, vol 14. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-21545-6_33
Download citation
DOI: https://doi.org/10.1007/978-3-662-21545-6_33
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-06841-9
Online ISBN: 978-3-662-21545-6
eBook Packages: Springer Book Archive