Relations Between Time and Tape Complexities

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Relations Between Time and Tape Complexities

Full text

Pdf (922 KB)

Source

Journal of the ACM (JACM) archive
Volume 15 , Issue 3 (July 1968) table of contents

Pages: 414 - 427

Year of Publication: 1968

ISSN:0004-5411

Authors

John E. Hopcroft	Cornell University, Ithaca, New York and Bell Telephone Laboratories, Inc., Murray Hill, New Jersey
Jeffrey D. Ullman	Bell Telephone Laboratories, Inc., Murray Hill, New Jersey

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 38, Citation Count: 3

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	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/321466.321474 What is a DOI?

ABSTRACT

It is shown that if a language L is recognized by a (nondeterministic) single-tape Turing machine of time complexity T(n), then L is recognized by a (nondeterministic) offline Turing machine of tape complexity T1/2(n). If T(n) ≥ n2;, L is recognized by a (nondeterministic) single-tape Turing machine of tape complexity T1/2(n). If a language L is recognized by a (nondeterministic) offline Turing machine of time complexity (T(n), then L is recognized by a (nondeterministic) offline Turing machine of tape complexity (T(n) log n)1/2 and by a (nondeterministic) single-tape Turing machine of that tape complexity if T (n) ≥ n2/log n.

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	HARTMANIS, J., AND STEARNS, R. E. Oil tile computatioltd complexity of dgorithms. Trans. Amer. Math. Soc. 117 (1965), 285-306.
	2	HARTMANIS, J., STEARNS, R. E., AND LEWIS, P. M., II. tIierarchies of memory limited computations. Proc. Sixth Annual Symposium on Switching Circuit Theory and Logical Design, IFEE, New York, Oct. 1965, pp. 179-190.
	3	HENNIE, F .C . Off-line Turing machine computtions. Inform. Contr. 8 (1965), 553-578.
	4	KURODA, S.V. Classes of languages and linear bounded automata. Inform. Contr. 7 (1964), 207-223.

CITED BY 3

	Dieter van Melkebeek , Ran Raz, A time lower bound for satisfiability, Theoretical Computer Science, v.348 n.2, p.311-320, 8 December 2005
	Ravi Kannan, Alternation and the power of nondeterminism, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.344-346, December 1983
	J. Hartmanis , J. E. Hopcroft, An Overview of the Theory of Computational Complexity, Journal of the ACM (JACM), v.18 n.3, p.444-475, July 1971