On Determinism Versus Non-Determinism And Related Problems

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. Introductio