Problem Solving in Automata, Languages, and Complexity

6.2 Time and Space Complexity 287

Proof. If we examine carefully the simulation of multi-tape DTM M by two-
way, one-tape DTM A& of Theorem 4.13, we can see that each move of M is
simulated by two passes over the entire tape configuration of 1M. Since the
size of the tape configuration is bounded by TimeM( each move of M takes
2Time~(x) + cllc moves to simulate, where k is the number of tapes of M
and cl is a constant. (The extra cl/c moves come from the adjustment of the
new tape symbols in each track done in the second pass.) It can be checked
that the initialization and ending stages take only time linear in the input
size. Therefore, the total time TimeM, is bounded by c(TimeM(~))~ for
some constant c > 0. cl

The above theorem shows that the time complexity functions of equivalent

DTM’s do not differ too much. For the space complexity, however, we need

to define the underlying model more carefully. A particular issue is that we

do not usually count the space occupied by the input as the work space in the

computation. Therefore, the space complexity of a one-tape DTM is difficult

to measure since the machine may or may not use the input space for the

computational purpose. So, in order to avoid this type of problem, we need

to distinguish between the work tapes and the input/output tapes. We say

a tape of a DTM M is an input tape if it is a read-only tape used to hold

the input symbols. The machine M is allowed to read the inputs on this

tape (more than once if it wants) but not to write over the input or blank

symbols. We say a tape of a DTM &! is an output tape if it is a write-only

tape used to print the output symbols. The machine M is only allowed to

write down the output symbol and then move the tape head to the right to

the next blank cell. The tape head of an output tape is not allowed to move

left. All other tapes are called work tapes or storage tapes. (A DTM may not

have the input tape or the output tape. For instance, a one-tape DTM has

only one work tape which is used to read inputs, to store temporary data, and

to write outputs.)

For any input string x, the memory space that a DTM M uses on x is the

number of cells on the work tapes which the tape head visits at least once

during the computation. We let SPUC,M(X) denote this number.

Similarly to the time complexity, we say a DTM i’U has a space bound s(n)

if for any input x,

SpuceM (2) 5 max{l, [s( 1x1)]}-4

Let us now fix a three-tape DTM model as a standard DTM model for space

complexity measure. Such a DTM has an input tape and a work tape. It may

or may not have the third output tape, depending on whether it needs to

produce outputs or not. We call such a DTM a standard one-worktape DTM,

or simply a one-worktape DTM. From the above definition, we only measure

4 We consi d e r only DTM’s that visit at least one cell of the work tapes.