Problem Solving in Automata, Languages, and Complexity

288 COMPUTATIONAL COMPLl3XsITY

the tape cells in the work tape that are visited by the tape head for the space

bound of such a DTM. The following theorem justifies our restriction to this

specific model as far as the space complexity is concerned.

Theorem 6.7 For any multi-tape DTM M, there is a standard one-worktape
DTM il.42 computing the same function such that SpaceM2 (x) < - SpaceM(x)
for all x.

Proof. We can design a one-worktape DTM Mz that simulates M as follows:

It uses the work tape to encode all work tapes of M, in the manner described

in Theorem 4.13. For each move of M, Mz reads the symbol currently scanned

by the input tape head, makes a pass over the work tape to collect the other

symbols currently scanned by M, and makes another pass over the work tape

to make changes on the work tape according to the instructions of M.

This is almost the same as DTM Ml of Theorem 4.13, except that Mz also

reads an input symbol and moves the input tape head. It is clear that the

space used by M2 is bounded by the total space used by M. 0

Using the one-worktape DTM model, the following result is trivial:

Theorem 6.8 For any one-worktape DTM M and any input x,

SpaceM (X) < - TimeM (x) + 1.

We now consider the time and space complexity of a decision problem,

based on the DTM model and the above defined time and space measures.

Let f : N + N be an integer function. We say a language has time complexity

f(n) if it is accepted by a multi-tape DTM with time bound f(n). We say a

language has space complexity f( n ) i i f t is accepted by a multi-tape DTM with

space bound f(n). For any function f(n), we define the following complexity

classes:

DTIME(f(n)) = {L 1 L has time complexity f(n)}.

DSPACE(f(n)) = {L 1 L has space complexity f(n)}.

It is clear that, for any function f(n), DTIME (f (n)) is a subclass of recursive

sets. This fact also holds, but not so obviously, for DSPACE (f (n)) (see

Exercise 1 of this section).

These time and space complexity classes have the following important prop-

erties. These properties allow us to use the standard asymptotic growth rates

f(n), such as logn, n 2, 2”) to define complexity classes without specifying the

coefficients of f(n).

• Theorem 6 9 (Tape Compression Theorem) For any function s(n) and
  any constant c’> 0,

DSPACE(s(n)) = DSPACE(c w s(n)).