Relations Between Time and Tape Complexities
John E. Hopcroft, Jeffrey David Ullman · Journal of the ACM · 1968
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 .