Quadratic lower bounds for deterministic and nondeterministic one-tape Turing machines

W. Maass

Abstract:

We introduce new techniques for proving quadratic lower bounds for deterministic and nondeterministic i-tape Turing machines (all considered Turing machines have an additional oneway input tape). In particular we produce quadratic lower bounds for the simulation of 2-tape TM's by l-tape TM's and thus answer a rather old question (problem No.1 and No.7 in the l i s t of Duris, Galil, Paul, Reischuk [3]). Further we demo6strate a substantial superiority of nondeterminism over determinism and of co-nondeterminism over nondeterminism for l-tape TM's.

Reference: W. Maass. Quadratic lower bounds for deterministic and nondeterministic one-tape Turing machines. In Proceedings of 16th Annual ACM Symp. on Theory of Computing, pages 401-408, 1984.