Problem Solving in Automata, Languages, and Complexity

6.2 Time and Space Complexity 293

By Theorem 6.10, DTIME(tl(n)) & DTIME(c. tz(n)) = DTIME(tz(n)).
Symmetrically, we have DTIME(tz(n)) C - DTIME(tl(n)). It follows that
DTIME(tl(n)) = DTIME(ta(n)). cl

Example 6.12 If c > 1, then for any c > 0, DTIME(cn) = DTIME((1 +

44 l

Proof. In the proof of Theorem 6.10, choose m > llc/~. Then

n+n + lO*

m

cn + 16 < n + (1 + 10~). ?- + 16 < (1 + &)n,

m - m -

for sufficiently large n.^0

Now that we have formally defined time and space complexity classes of
languages, which of these classes are feasible classes? Unfortunately, this ques-
tion again depends on the specific computational models we use. Although
we have shown, in Chapter 4, that machines in different models can simulate
each other so that the class of computable functions is the same for these ma-
chines, it is conceivable that one type of machine may run faster or use less
work space than the other type. The empirical studies on these computational
models, however, indicates that these simulations can often be done within a
polynomial factor. That is, if one type of machines can accept a language in
time t(n), the other type of machines can accept it in time (t(n))c for some
constant c > 0. For instance, Theorem 6.6 shows that one-tape DTM’s can
simulate multi-tape DTM’s within a time factor of n2. These studies sup-
port the following extended version of the Church-Turing Thesis, though the
support is not as strong as that for the Church-Turing Thesis.

Extended Church-Turing Thesis. A function computable in polynomial
time in any reasonable computational model using a reasonable time complex-
ity measure is computable by a deterministic Turing machine in polynomial
time.

Now, let us define the following complexity classes:

P= u DTIME(n”).

c>o

EXP = u DTIME(2”“).

00

EXPPOLY = u DTIME(2nC).

c>o

PSPACE = U DSPACE(nC).

c>o