Relations Between Time and Tape Complexities
- 1 July 1968
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 15 (3) , 414-427
- https://doi.org/10.1145/321466.321474
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 T 1/2 ( n ). If T ( n ) ≥ n 2 ;, L is recognized by a (nondeterministic) single-tape Turing machine of tape complexity T 1/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 ) ≥ n 2 /log n .Keywords
This publication has 2 references indexed in Scilit:
- One-tape, off-line Turing machine computationsInformation and Control, 1965
- Classes of languages and linear-bounded automataInformation and Control, 1964