Quadratic lower bounds for deterministic and nondeterministic one-tape turing machines
Wolfgang Maass · 1984
We introduce new techniques for proving quadratic lower bounds for deterministic and nondeterministic l-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 list of Duris, Galil, Paul, Reischuk [3]). Further we demonstrate a substantial superiority of nondeterminism over determinism and of co-nondeterminism over nondeterminism for l-tape TM's.