An NP-complete language accepted in linear time by a one-tape Turing machine

AbstractWe consider one-tape nondeterministic Turing machines, i.e. with a unique worktape on which the input is written. It is known that there are nonregular languages accepted by such machines in time O(n log log n), and an NP-complete language accepted in time O(n log n). We exhibit nonregular languages accepted by such machines in time n + O(√nlogn) or n + O(log2 n), and an NP-complete language accepted in time n + O(√nlogn, by using a tight padding method