On determinism versus non-determinism and related problems
Wolfgang J. Paul, Nicholas J. Pippenger, Endre Szemerédi, William T. Trotter · 1983
We show that, for multi-tape Turing machines, non-deterministic linear time is more powerful than deterministic linear time. We also discuss the prospects for extending this result to more general Turing machines.