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

We discuss the following family of problems, parameterized by integers $C\geq 2$and$D\geq 1$:Doesagivenone-tapenon-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)\mathrm{/}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)\mathrm{/}2})$ non-deterministic time by multi-tape Turing machines.