Problem Solving in Automata, Languages, and Complexity

6.3 Hierarchy Theorems 301

B/B, L B/B, R

B/B, R B/B, R

Figure 6.5: (n + a)” is fully time-constructible.

4.13, where we showed how to simulate a k-tape DTM by a one-tape DTM in

time O((~&J))~), if the k-tape DTM halts in time tl(n). This simulation can

be modified to run in time only O(t 1 (n) lo& (n))), if we allow the simulator

M* to have two tapes. (The second tape can be used to move data around

more efficiently. The exact simulation is too complicated, and we omit it

here.) So, if we allow M* to have at least two tapes and if its running time

t2 (n) grows faster than t 1 (n) lo&(n)), then &!* can simulate at least tl (n)

moves of A&, and the diagonalization works. Cl

In order to apply the hierarchy theorems to specific complexity classes,

we first need to know which functions are fully space or time constructible.

It turns out that almost all familiar functions, including those in the five

sequences defined in Section 6.1, are fully time and space constructible. In

the following, we demonstrate this result on two simple functions.

Example 6.18 Show that (n + 2)2 is fully time-constructible.

SoZution. We construct a one-tape DTM M which has a singleton input

symbol set { 1) and the tape symbol set { 1, B, a}. It works as follows: It moves

back and forth between the two blanks surrounding the nonblank symbols,

each time changing one input symbol 1 into symbol a. After the last round in

which it cannot find any symbol 1, it moves back and forth two more times.

The complete transition diagram of M is shown in Figure 6.5. Note that a

complete trip from the blank at one end to the blank of the other end takes

n + 1 moves. Also note that the total number of trips made by the tape