Complexity Classes - Models of Computation: Exploring the Power of Computing - page 341

Each of the vertices (configurations) adjacent to a particular vertex can be deduced from the
description of M ND .

Since the number of configurations of M ND is N = O k log n + r ( n ) , each configura-
tion or activation record can be stored as a string of length O ( r ( n )) .
From Theorem 8.5.5 , the reachability in G ( M ND , w ) of the final configuration from

the initial one can be determined in space O (log 2 N ) .But N = O k log n + r ( n ) ,from
which it follows that NSPACE ( r ( n ))

⊆

SPACE ( r 2 ( n )) .

The classes NL , L 2 and PSPACE are defined as unions of deterministic and nondetermin-
istic space-bounded complexity classes. Thus, it follows from this corollary that NL L 2 ⊆

PSPACE . However, because of the space hierarchy theorem (Theorem 8.5.2 ), it follows that
L 2 is contained in but not equal to PSPACE , denoted L 2

⊆

⊂ PSPACE .

8.5.4 Relations Between Time- and Space-Bounded Classes
In this section we establish a number of complexity class containment results involving both
space- and time-bounded classes. We begin by proving that the nondeterministic O ( r ( n )) -

space class is contained within the deterministic O k r ( n ) -time class. This implies that NL

⊆

⊆

P and NPSPACE EXPTIME .

THEOREM 8.5.6 The classes NSPACE ( r ( n )) and TIME ( r ( n )) of decision problems solvable in
nondeterministic space and deterministic time r ( n ) , respectively, satisfy the following relation for
some constant k> 0 :

TIME ( k log n + r ( n ) ) NSPACE ( r ( n ))

⊆

Proof Let M ND accept a language L

( r ( n )) and let G ( M ND , w ) be the
configuration graph for M ND on input w . To determine if w is accepted by M ND and
therefore in L , it suffices to determine if there is a path in G ( M ND , w ) from the initial
configuration of M ND to the final configuration. This is the REACHABILITY problem,
which, as stated in the proof of Theorem 8.5.5 , can be solved by a DTM in time polynomial
in the length of the input. When this algorithm needs to determine the descendants of a
vertex in G ( M ND , w ), it consults the definition of M ND to determine the configurations
reachable from the current configuration. It follows that membership of w in L can be

∈ NSPACE

determined in time O k log n + r ( n ) for some k> 1orthat L is in TIME k log n + r ( n ) .

COROLLARY 8.5.2 NL ⊆ P and NPSPACE ⊆ EXPTIME

Later we explore the polynomial-time problems by exhibiting other important complexity
classes that reside inside P .(SeeSection 8.15 .) We now show containment of the nondeter-
ministic time complexity classes in deterministic space classes.

THEOREM 8.5.7 The following containment holds:

SPACE ( r ( n ))
Proof We use the construction of Theorem 5.2.2 .Let L be a language in NTIME ( r ( n )) .
We note that the choice string on the enumeration tape converts the nondeterministic recog-
nition of L into deterministic recognition. Since L is recognized in time r ( n ) for some
accepting computation, the deterministic enumeration runs in time r ( n ) for each choice

NTIME ( r ( n ))

⊆