A language L is said to be a member of the class NTIME (T(n)) if there exists
a nondeterministic multitape Turing machine that decides L in time O(T(n)).
Some relations between these complexity classes, such as
DTIME (T(n)) ⊆ NTIME (T (n)),
and
T1(n) = O(T 2 (n))
implies
DTIME (T 1 (n)) ⊆ DTIME (T 2 (n)),
are obvious, but from here the situation becomes obscure quickly. What we can
say is that as the order of T(n) increases, we take in progressively more
languages.
Theorem 14.3
For every integer k ≥ 1,
DTIME (n k ) ⊂ DTIME (n k+1 ).
Proof: This follows from a result in Hopcroft and Ullman (1979, p. 299).
The conclusion we can draw from this is that there are some languages that
can be decided in time O(n 2 ) for which there is no linear-time membership
algorithm, that there are languages in DTIME (n 3 ) that are not in DTIME (n 3 ),
and so on. This gives us an infinite number of nested complexity classes. We get
even more if we allow exponential time complexity. In fact, there is no limit to
this; no matter how rapidly the complexity function T (n) grows, there is always
something outside DTIME (T(n)).
Theorem 14.4