Verifying whether One-Tape Non-Deterministic Turing Machines Run in Time $Cn+D$

Abstract

We discuss the following family of problems, parameterized by integers $C\ge 2$ and $D\ge 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.

12 pages + 5 pages appendix

References in corpus (1)

• Verifying Time Complexity of Deterministic Turing Machines