On the structure of one-tape nondeterministic Turing machine time hierarchy (Q1082813)

We show that if the number of available states is fixed and is sufficiently large, then one-tape nondeterministic Turing machines can accept more sets within time bound \(a_ 2f(n)\) than within \(a_ 1f(n)\), for \(0<a_ 1<a_ 2\). Here, f(n) is any function of the form \(n^{b_ 0}(\log n)^{b_ 1}(\log^ 2n)^{b_ 2}...(\log^ hn)^{b_ h}\) \((b_ 0,...,b_ h\) are rational numbers) with order between n log n and \(n^ 2\). Crossing sequences and Kolmogorov complexity are used to prove it.