On Time Versus Space
Open accessAbstract
It is shown that every deterministic multitape Turing machine of time complexity t ( n ) can be simulated by a deterministic Turing machine of tape complexity t ( n )/log t ( n ). Consequently, for tape constructable t ( n ), the class of languages recognizable by multitape Turing machines of time complexity t ( n ) is strictly contained in the class of languages recognized by Turing machines of tape complexity t ( n ). In particular the context-sensitive languages cannot be recognized in linear time by deterministic multitape Turing machines.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The time lower bound and space upper bound are fairly tight: improving either by a factor larger than log t(n) would result in a fundamental complexity theory advance.
“Both our time lower bound and space upper bound are fairly tight: improving either by a factor larger than log t(n) would result in a fundamental complexity theory advance (Hopcroft et al., 1977).”
From The expressive power of transformers with chain of thought (2023) · cites this paper as Hopcroft et al., 1977
The Introduction reports that deterministic time t(n) is contained in deterministic space t(n)/log t(n), establishing the logarithmic relationship invoked by the citation. It does not assess the citing authors’ time lower bound or space upper bound, or state that improving either by more than log t(n) would constitute a fundamental advance. (LLM, conf=0.78)
Experimental — accuracy not yet measuredGiven the TIME(t(n)) lower bound, the tightest possible space upper bound without making fundamental complexity advances would be SPACE(t(n)/ log t(n)).
“Given our TIME(t(n)) lower bound (Theorem 2), the tightest possible space upper bound without making fundamental complexity advances would be SPACE(t(n)/ log t(n)) (Hopcroft et al., 1977).”
From The expressive power of transformers with chain of thought (2023) · cites this paper as Hopcroft et al., 1977
The Introduction (page unavailable) states that deterministic time t(n) is contained in space t(n)/log t(n), supporting the proposed space upper bound. The paper does not establish that this is the tightest possible upper bound or that improving it would require fundamental complexity advances. (LLM, conf=0.85)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
No references could be resolved yet.
Research works printed but not linked: 11
- Atto, A.V, HOPCROVr, J.E., AND ULLMAN, J D. The Design and Analysis of Computer Algorithms Addison-Wesley, Reading, Mass , 1974
- CooK. S A An observation of nine-storage trade-off Proc. Fifth Annual ACM Syrup. on Theory of Comput, 1973, pp. 29-33
- HARTMANIS, J , AND STEARNS, R E On the computational complexity of algorithms. Trans. Amer Math Soc 117 (1965), 285-306
- HENNIE, F.C On-hne Turlng machine computations 1EEE Trans. Electronic Computers EC-15 (1966), 35-44
- HENNIE, F C , AND STEARNS, R E Two-tape simulation of multitape Turmg machines. J ACM 13, 4 (Oct 1966), 533-546
- HOPCROFT, J E , AND ULLMAN, J D Some results on tape-bounded Turlng machines. J ACM 16, 1 (Jan 1969),168-177
- HOPCRO~, J E , AND ULLMAN, J D Formal Languages and Their Relatton to Automata. Addison- Wesley, Reading, Mass , 1969
- PATERSON, M S Tape bounds for time-bounded Turmg machines. J Computer System Sct. 6 (1972), 116-124
- SAvrrcrt, W J Relationships between nondetermlmstic and deterministic tape complexltleg. J. Com- puter System Sct 4, 2 (1970), 117-192 ]
- STEARNS, R E , HARTMANIS, J , AND LEWIS, P M Hierarchies of memory hmited computations Proc Sixth IEEE Syrup. on Switching and Automata Theory, 1965, pp. 191-202.
- RECEIVED NOVEMnER 1975, REVISED ~AV 1976 Journal of the Assoclatlon for Computing Machinery, Vol 24, No 2. April 1977
Cited by
Sorted by citations
Dziembowski, S., Faust, S., Kolmogorov, V., & Pietrzak, K. (2015) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-48000-7_29 · Cited by 294 · see citing works
The expressive power of transformers with chain of thought
Merrill, W., & Sabharwal, A. (2023) · arXiv · doi:10.48550/arxiv.2310.07923 · Cited by 4 · see citing works
- Authors
- Hopcroft, J., Paul, W., & Valiant, L.
- Affiliations
- Cornell University (US)
- Bielefeld University (DE)
- University of Leeds (GB)
- ORCID
- Hopcroft, John
- Venue
- Journal of the ACM
- Published
- 1977-04
- Volume
- 24
- Issue
- 2
- Pages
- 332-337
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W2062934582
- Cited by
- 253
- References
- 0
- Citations by year
- 2026: 4 · 2025: 6 · 2024: 2 · 2022: 2 · 2021: 2 · 2020: 2 · 2019: 2 · 2018: 5 · 2017: 6 · 2016: 6 · 2015: 10 · 2014: 3 · 2013: 16 · 2012: 4
- FWCI
- 21.55
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Journal of the ACM (publishedVersion)
- eCommons (Cornell University) (submittedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
- Physical Sciences › Computer Science › Artificial Intelligence › Algorithms and Data Compression
- Keywords
- multitape Turing machines, deterministic Turing machines, time complexity, simulation, context-sensitive languages, linear-time recognition, complexity classes
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
