Document Type
Article - preprint
Department
Mathematics (HMC)
Publication Date
1983
Abstract
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
Rights Information
© 1989 IEEE
Terms of Use & License Information
Recommended Citation
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).