Tape-bounds for time-bounded Turing machines
Michael Stewart Paterson · 1970
Let L be a language recognized by a nondeterministic (single-tape) Turing machine of time complexity T(n)>=n^2. Then L is also recognized by a deterministic (single-tape) Turing machine of tape complexity T^1^/^2(n).