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

⊆ ⊆

The relationships P NP and EXPTIME NEXPTIME are examples of a more general

result, namely, TIME ( r ( n )) NTIME ( r ( n )) , where these two classes of decision problems

can respectively be solved deterministically and nondeterministically in time r ( n ) ,where n
is the length of the input. This result holds because every

⊆

TIME ( r ( n )) of length n is
accepted in r ( n ) steps by some DTM M P and a DTM is also a NDTM. Thus, it is also true
that

P∈

P∈

NTIME ( r ( n )) .

8.5.3 Space-Bounded Complexity Classes
Many other important space complexity classes are defined by the amount of space used to
recognize languages and compute functions. We highlight five of them here: the determin-
istic and nondeterministic logarithmic space classes L and NL , the square-logarithmic space
class L 2 , and the deterministic and nondeterministic polynomial-space classes PSPACE and
NPSPACE .

DEFINITION 8.5.4 L and NL are the decision problems solvable in logarithmic space on a DTM
and NDTM, respectively. L 2 are the decision problems solvable in space O (log 2 n ) on a DTM.
PSPACE and NPSPACE are the decision problems solvable in polynomial space on a DTM and
NDTM, respectively.

Because L and PSPACE are deterministic complexity classes, they are contained in NL and
NPSPACE , respectively: that is, L NPSPACE .

We now strengthen the latter result and show that PSPACE = NPSPACE ,whichmeans
that nondeterminism does not increase the recognition power of Turing machines if they al-
ready have access to a polynomial amount of storage space.
The REACHABILITY problem on directed acyclic graphs defined below is used to show this
result. REACHABILITY is applied to configuration graphs of deterministic and nondetermin-
istic Turing machines. Configuration graphs are introduced in Section 5.3 .

⊆ NL and PSPACE ⊆

REACHABILITY
Instance: Adirectedgraph G =( V , E ) and a pair of vertices u , v

∈ V .

Answer: “Yes” if there is a directed path in G from u to v .

REACHABILITY can be decided by computing the transitive closure of the adjacency matrix
of G in parallel. (See Section 6.4 .) However, a simple serial RAM program based on depth-
first search can also solve the reachability problem. Depth-first search (DFS)onanundirected
graph G visits each edge in the forward direction once. Edges at each vertex are ordered. Each
time DFS arrives at a vertex it traverses the next unvisited edge. If DFS arrives at a vertex from
which there are no unvisited edges, it retreats to the previously visited vertex. Thus, after DFS
visits all the descendants of a vertex, it backs up, eventually returning to the vertex from which
the search began.
Since every T -step RAM computation can be simulated by an O ( T 3 ) -step DTM computa-
tion (see Problem 8.6 ), a cubic-time DTM program based on DFS exists for REACHABILITY .
Unfortunately, the space to execute DFS on the RAM and Turing machine both can be linear
in the size of the graph. We give an improved result that allows us to strengthen PSPACE ⊆

NPSPACE to PSPACE = NPSPACE .
Below we show that REACHABILITY can be realized in quadratic logarithmic space. This
fact is then used to show that NSPACE ( r ( n ))

SPACE ( r 2 ( n )) for r ( n )=Ω(log n ) .

⊆