Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR15-036 | 17th February 2015 17:10

Verifying whether One-Tape Turing Machines Run in Linear Time


Authors: David Gajser
Publication: 11th March 2015 05:57
Downloads: 1034


We discuss the following family of problems, parameterized by integers $C\geq 2$ and $D\geq 1$: Does a given one-tape non-deterministic $q$-state Turing machine make at most $Cn+D$ steps on all computations on all inputs of length $n$, for all $n$?

Assuming a fixed tape and input alphabet, we show that these problems are co-NP-COMPLETE and we provide good non-deterministic and co-non-deterministic lower bounds. Specifically, these problems can not be solved in $o(q^{(C-1)/4})$ non-deterministic time by multi-tape Turing machines. We also show that the complements of these problems can be solved in $O(q^{C+2})$ non-deterministic time and not in $o(q^{(C-1)/2})$ non-deterministic time by multi-tape Turing machines.

Up to constant factors in the exponents all of the above results hold also if we restrict our input only to deterministic one-tape Turing machines.

ISSN 1433-8092 | Imprint