286 COMPUTAT1ONAL COMPLEXITY
- Prove that log@+‘) 4 log(“) n for any k > - 0.
- Denote log* n = min{Ic 1 (log)% < - 1, k
log* 12. - Recall the Ackermann function A defined
(a) Compare the function f(n) = A(n, n)
(b) Compare the function g(n) = max{k 16.2 Time and Space Complexity
> - 1). Compare log** n withn Exercise 8 of Section 4.8.with 22”.
A(k, Ic) < - n} with log* n.Computational complexity of a Turing machine studies the computational
resources required for a Turing machine to solve a problem. Computation
time and space are the two most important computational resources for Turing
machines. Therefore, it is critical to study the class of Turing machines with
limited running time and/or memory space.
For an input string X, the running time of a DTM M on II: is the number
of moves M takes to halt on input X, that is, the number of configurations
in the computation from the initial configuration with x as the input to a
halting configuration. We denote this number by Time&r) (if M does not
halt on X, then TimeM (z) = 00). Based on the asymptotic view of Section
6.1, we group the inputs of the same length together and consider the running
time on them as a single function. That is, assume that t(n) > - n + 1 for
sufficiently large n. 3 Then, we say M has a time bound t(n) if for all inputs
z with 151 < - n,
TimeM 5 max{n + 1$(n)}.
Recall that we defined several different models of Turing machines in Chap-
ter 4. It is apparent that a single problem may have different running time
when it is solved using different models of DTM’s. In particular, a multi-
tape DTM seems to have a lower time bound than an equivalent one-tape
DTM (cf. Example 4.13). Therefore, when we compare the time complexity
of two problems, we need to make sure that they are compared within the
same model; that is, we need to be concerned with the implementation of an
algorithm in a particular model of DTM’s. Fortunately, the following theorem
shows that the running time functions of different models of DTM’s do not
differ too much.
Theorem 6.6 For any multi-tape DTM M, there exists a two-way, one-tape
DTM Ml computing the same function such that for all inputs x, we have
TimeM, (x) 5 c l (TirneM(~))~ for some constant c > 0.
3 We consider only DTM’s that always read all its input symbols before it halts. Thus,
we consider only func tions t(n) 2 n + 1 as time boun ds.