Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR15-036 | 17th February 2015 17:10

Verifying whether One-Tape Turing Machines Run in Linear Time

RSS-Feed




TR15-036
Authors: David Gajser
Publication: 11th March 2015 05:57
Downloads: 2693
Keywords: 


Abstract:

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