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.

Share

COinS