An Overview of the Theory of Computational Complexity

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An Overview of the Theory of Computational Complexity

Full text

Pdf (2.06 MB)

Source

Journal of the ACM (JACM) archive
Volume 18 , Issue 3 (July 1971) table of contents

Pages: 444 - 475

Year of Publication: 1971

ISSN:0004-5411

Authors

J. Hartmanis	Cornell University, Department of Computer Science, Ithaca, New York
J. E. Hopcroft	Cornell University, Department of Computer Science, Ithaca, New York

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 88, Citation Count: 14

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321650.321661 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	AXT, P. Enumeration and the Grzegorczyk hierarchy. Z. Math. Logik Grundlagen Math. 9 (1963), 53-65.
	2	BECVAR, J. Real-time and complexity problems in automata theory. Kybernetika 1 (1965), 475--497.
	3	Manuel Blum, On effective procedures for speeding up algorithms, Proceedings of the first annual ACM symposium on Theory of computing, p.43-53, May 05-07, 1969, Marina del Rey, California, United States [doi>10.1145/800169.805420]
	4	BORODIN, A., CONSTABLE, R. L., AND HOPCROFT, J .E . Dense and nondense families of complexity classes. IEEE Conf. Rec. Tenth Ann. Symp. on Switching and Automata Theory, 1969, pp. 7-19.
	5	COBHAM, A. On the Hartmanis-Stearns problem for a class of tag machines. IEEE Conf. Rec. Ninth Ann. Symp. on Switching and Automata Theory, 1968, pp. 51-60.
	6	CONSTABLE, R.L. The operator gap. IEEE Conf. Rec. Tenth Ann. Symp. on Switching and Automata Theory, 1969, pp. 20-26.
	7	Patrick C. Fischer, Multi-tape and infinite-state automata—a survey, Communications of the ACM, v.8 n.12, p.799-805, Dec. 1965 [doi>10.1145/365691.365962]
	8	FISCHER, P. C. The reduction of tape reversals for off-line one-tape Turing machines," J. Computer Systems Sciences 2 (1968), 136-147.
	9	FISCHER, P. C., HARTMANIS J. AND BLUM M. Tape reversal complexity hierarchies. IEEE Conf. Rec. Ninth Ann. Syrup. on Switching and Automata Theory, 1968, pp. 373-382.
	10	GRZEGORCZYK, A. Some classes of recursive functions. Rozprawy Mat. $, Warsaw, (1953), 1-45.
	11	HARTMANIS, J. Tape reversal bounded Turing machine computations. J. Computer Systems Sciences 2 (1968), 117-135.
	12	HENNIE, F. C. One-tape, off-line Turing machine computations. Inf. Conlr. 8 (1965), 553- 578.
	13	HENNIE, F. C. Crossing sequences and off-line Turing machine computations. 1965 IEEE Conf. Rec. on Switching Circuit Theory and Logical Design, pp. 168-172.
	14	John E. Hopcroft , Jeffrey D. Ullman, Relations Between Time and Tape Complexities, Journal of the ACM (JACM), v.15 n.3, p.414-427, July 1968 [doi>10.1145/321466.321474]
	15	J. E. Hopcroft , J. D. Ullman, Some Results on Tape-Bounded Turing Machines, Journal of the ACM (JACM), v.16 n.1, p.168-177, Jan. 1969 [doi>10.1145/321495.321508]
	16	IRLAND, M. I., AND FISCHER, P.C. A bibliography on computational complexity. Res. Rep. CSRR 2028, U. of Waterloo, Ontario, Canada, Oct. 1970.
	17	Richard M. Karp, Some Bounds on the Storage Requirements of Sequential Machines and Turing Machines, Journal of the ACM (JACM), v.14 n.3, p.478-489, July 1967 [doi>10.1145/321406.321410]
	18	LEwis, P. M. II, STEARNS, R. E., AND HARTMANIS, J. Memory bounds for recognition of context-free and context-sensitive languages. 1965 IEEE Conf. Rec. on Switching Circuit Theory and Logical Design, pp. 191-202.
	19	Edward M. Mccreight, Classes of computable functions defined by bounds on computation, 1969
	20	Albert R. Meyer , Dennis M. Ritchie, The complexity of loop programs, Proceedings of the 1967 22nd national conference, p.465-469, January 1967, Washington, D.C., United States [doi>10.1145/800196.806014]
	21	RABIN, M.O. Real time computation. Israel J. Math. I (1964), 203-211.
	22	RITCHIE, R.W. Classes of predictably computable functions. Trans. Amer. Math. Soc. 106 (1963), 139-173.
	23	Walter J. Savitch, Deterministic simulation of non-deterministic turing machines (Detailed Abstract), Proceedings of the first annual ACM symposium on Theory of computing, p.247-248, May 05-07, 1969, Marina del Rey, California, United States [doi>10.1145/800169.805439]
	24	TRAKHTENBROT, B.A. Turing computations with logorithmie delay. Algebra i Logika 3, ~, in Russian, (1964), 33-48.
	25	YAMADA, H. Real-time computation and recursive functions not real-time computable," IRE Trans. Elec. Comp. EC-11 (1962), 753-760.

CITED BY 14

	H. B. Hunt, III, On the Decidability of Grammar Problems, Journal of the ACM (JACM), v.29 n.2, p.429-447, April 1982
	R. L. Constable , J. Hartmanis, Complexity of formal translations and speed-up results, Proceedings of the third annual ACM symposium on Theory of computing, p.244-250, May 03-05, 1971, Shaker Heights, Ohio, United States
	J. Hartmanis, Relations between diagonalization, proof systems, and complexity gaps, Proceedings of the ninth annual ACM symposium on Theory of computing, p.223-227, May 04-04, 1977, Boulder, Colorado, United States
	Shimon Even , Alan L. Selmen , Yacov Yacobi, Hard-core theorems for complexity classes, Journal of the ACM (JACM), v.32 n.1, p.205-217, Jan. 1985
	Robert L. Constable , Allan B. Borodin, Subrecursive Programming Languages, Part I: efficiency and program structure, Journal of the ACM (JACM), v.19 n.3, p.526-568, July 1972
	H. B. Hunt, III, A complexity theory of grammar problems, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.12-18, January 19-21, 1976, Atlanta, Georgia
	H. B. Hunt, III , T. G. Szymanski, On the complexity of grammar and related problems, Proceedings of seventh annual ACM symposium on Theory of computing, p.54-65, May 05-07, 1975, Albuquerque, New Mexico, United States
	Kurt Mehlhorn, Polynomial and abstract subrecursive classes, Proceedings of the sixth annual ACM symposium on Theory of computing, p.96-109, April 30-May 02, 1974, Seattle, Washington, United States
	Robert L. Constable, Type two computational complexity, Proceedings of the fifth annual ACM symposium on Theory of computing, p.108-121, April 30-May 02, 1973, Austin, Texas, United States
	Leonard Bass , Paul Young, Ordinal Hierarchies and Naming Complexity Classes, Journal of the ACM (JACM), v.20 n.4, p.668-686, Oct. 1973
	Marian Boykan Pour-El, Computer Science And Recursion Theory, Proceedings of the 1978 annual conference, p.15-20, December 04-06, 1978, Washington, D.C., United States
	Mark Burgin, Algorithmic complexity of recursive and inductive algorithms, Theoretical Computer Science, v.317 n.1-3, p.31-60, June 4, 2004
	Andrzej Salwicki, Andrzej Grzegorczyk's Contribution to Computer Science, Fundamenta Informaticae, v.81 n.1-3, p.315-323, January 2007
	Patrick C. Fischer, Theory of computing in computer science education, Proceedings of the November 16-18, 1971, fall joint computer conference, November 16-18, 1971, Las Vegas, Nevada