Article - preprint
We show that, for multi-tape Turing machines, non-deterministic linear time is more deterministic Turing machines (that receive their input on their work tape) require time Q(n2) to powerful than deterministic linear time. We also recognize non-palindromes of length n (it is easy to discuss the prospects for extending this result to see that time O(n log n) is. sufficient for a more general Turing machines. non-deterministic machine). 1. Introduction
© 1989 IEEE
W. J. Paul, N. Pippenger, E. Szemeredi, W. T. Trotter, On Determinism Versus Non-Determinism And Related Problems, IEEE Symp. on Foundations of Comp. Sci., 24, 429-438 (1983).