Problem Solving in Automata, Languages, and Complexity

6.3 Hierarchy Theorems 297

(b) Let ASCB = {x E l(O+ l) +0 1 n(z) = n(y) n(z) for some y E A

and x E B}. Show that if A, B E PSPACE then A * B is also in

PSPA CE.

* (c) Assume that A, B E P. Is it true that A + B is also in P? Is it

true that A SC B is also in P?

6.3 Hierarchy Theorems

Suppose that two functions f(n) and g(n) satisfy that f(n) + g(n). Then,

intuitively, Turing machines with the time bound g(n) are more powerful

than Turing machines with the time bound f(n), in the sense that the

machines with time bound g(n) can compute some functions or languages

that are not computable by machines with time bound f(n). That is,

we expect that DTIME(g(n)) \ DTIME(f(n)) # 8. Likewise, we expect

DSPACE(g(n)) \ DSPACE(f(n)) $5 8. Th is is, however, not always true. It is

known that there are some ill-behaved functions f and g satisfying f(n) 4 g(n)

but DTIME(g(n)) = DTIME(f(n)) (called the gap theorem).

In this section, we show that this intuitive expectation is indeed correct,

as long as the functions f and g are well behaved and that g(n) grows faster

than f(n) log f(n). I n order to describe these results, we first need to define

two classes of well-behaved functions. We say that a function s(n) is fully

spuce-constructible if there exists a DTM M such that for sufficiently large

integers n and any input x with 1x1 = n, Space&z) = s(n). Thus, if s(n)

is fully space-constructible, then we can simulate this DTM on any input x

of length n to mark off exactly s(n) cells in the work tapes. We call such a

DTM a s(n)-space marking machine.

* Theorem 6.16 (Space Hierarchy Theorem) Let sz(n) be a fully space con-

structible function. Suppose that liminf,,,, sl(n)/sz(n) = 0 and sl(n) >

log n. Then,

DSPACE(s:!(n)) \ DSPACE(sl(n)) # 8.

Proof. We need to construct a language L which is in DSPACE (s2 (n)) but

not in DSPACE(sl(n)). Th e b asic tool is a refined, space-bounded version of

diagonalization. The setup for diagonalization is as follows:

Since any multi-tape DTM can be simulated by a standard one-worktape

DTM within the same space, we need only consider all one-worktape DTM’s.

We enumerate all such DTM’s Mw with space bound q(n) (recall that Mw

is the DTM whose code is w), and try to construct a new DTM M* which

has space bound sz(n) and satisfies L(M*) # L(&) for all M,. That is, the

DTM M* needs to satisfy the following requirements:

R,: L(M) # L(NI,), for all w E {O,l} such that A& has a space

bound s1 (n).

R’: 1M* has the space bound sz(n).