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 ... more >>>