On Determinism Versus Non-Determinism And Related Problems

Authors

Wolfgang J. Paul, IBM Research Laboratory
Nicholas Pippenger, Harvey Mudd CollegeFollow
Endre Szemeredi, University of South Carolina
William T. Trotter, University of South Carolina

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

Terms of Use for work posted in Scholarship@Claremont.

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