The central problem in the dissertation is the following.
For a function $T:\mathbb{N}\rightarrow\mathbb{R}^+$, how hard is it to verify whether a given Turing machine runs in time at most $T(n)$? Is it even possible?
Our first main contibution is that, for all reasonable functions $T(n)=o(n\log n)$, it is possible to verify with an algorithm whether a given one-tape Turing machine runs in time at most $T(n)$. This is a tight bound on the order of growth for the function $T$ because we prove that, for $T(n)=\Omega(n\log n)$ and $T(n)\geq n+1$, there exists no algorithm that would verify whether a given one-tape Turing machine runs in time at most $T(n)$.
As opposed to one-tape Turing machines, we show that we can verify with an algorithm whether a given multi-tape Turing machine runs in time at most $T(n)$ if and only if $T(n_0)< n_0+1$ for some $n_0\in\mathbb{N}$.
Linear time bounds are the most natural algorithmically verifiable time bounds for one-tape Turing machines, because a one-tape Turing machine that runs in time $o(n\log n)$ actually runs in linear time. This motivates our second main contibution which is the analysis of complexity of the following family of problems, parameterized by integers $C\geq 2$ and $D\geq 1$:
Does a given one-tape $q$-state Turing machine run in time $Cn+D$?
Assuming a fixed tape and input alphabet, we show that these problems are co-NP-complete and we provide good lower bounds. Specifically, these problems cannot 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)/4})$ non-deterministic time by multi-tape Turing machines.
To prove the upper bound $O(q^{C+2})$, we use the so-called compactness theorem which is our third main contribution. We need more notation to state it in full generality, but a simple corollary tells the following: To verify whether an input one-tape Turing machine runs in time $Cn+D$, it is enough to verify this on a finite number of inputs.
1 Introduction 2 Preliminaries 3 Turing Machines 4 Diagonalization and Relativization 5 Crossing Sequences 6 Verifying Time Complexity of Turing Machines
