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

- DIST - FROM - u , which examines and counts all pos-
sible next to last node s reachable from u .#- VERTICES - AT -

≤

value to the procedure IS - NODE - AT -

≤

- DISTANCE - FROM - u ei-

ther fails to find all possible vertices at distance dist

−

1, in which case it fails, or finds all
such vertices. Thus, it nondeterministically verifies that all possible paths from u have been
explored. IS - NODE - AT -

≤

- DIST - FROM - u uses the procedure EXISTS - PATH - FROM - u - TO -

v - ≤

- LENGTH that either correctly verifies that a path of length dist

−

1existsfrom u to

next to last node or fails. In turn, EXISTS - PATH - FROM - u - TO - v - ≤

- LENGTH uses the
command NONDETERMINISTIC - GUESS ([ 1, .. , n ]) to nondeterministically choose nodes
on a path from u to v .
Since this program is not recursive, it uses a fixed number of variables. Because these
variables assume values in the range [ 1, 2, 3, ... , n ] , it follows that space O (log n ) suffices
to implement it on an NDTM.

We now extend this result to nondeterministic space computations.

COROLLARY 8.6.2 If r ( n )=Ω(log n ) is proper, NSPACE ( r ( n )) = coNSPACE ( r ( n )) .

Proof Let L ( r ( n )) be decided by an r ( n ) -space bounded NDTM M .We

show that the co mp lement of L can be decided by a nondeterministic r ( n ) -space bounded
Turing machine M , stopping on all inputs. We modify slightly the program of Fig. 8.9 for
this purpose. The graph G is the configuration graph of M . Its initial state is determined
by the string w that is initially written on M 's input tape. To determine adjacency bet wee n
two vertices in the configuration graph, computations of M are simulated on one of M 's
wor k t apes.
M computes a slightly modified version of COUNTING - REACHABILITY .First,ifthe
procedure IS - NODE - AT - LENGTH -

∈ NSPACE

- DIST - FR OM - u returns true for a vertex u that is a
halting accepting configuration of M ,then M halts and rejects the string. If the proced ure
COUNTING - REACHABILITY completes successfully without rejecting any string, then M
halts and accepts the input string because every possible accepting computation for the input
string has been examined and none of them is accepting. This computation is nondetermin-
istic.
The space used by M is the space needed for COUNTING - REACHABILITY ,which
means it is O (log N ) ,where N is the number of vertices in the configuration graph of
M plus the space for a simulation of M ,whichis O ( r ( n )) .Since N = O ( k log n + r ( n ) )
(see the proof of Theorem 8.5.6 ), the total space for thi s c omputation is O (log n + r ( n )) ,
which is O ( r ( n )) i f r ( n )=Ω(log n ) .Bydefinition L

≤

∈ coNSPACE ( r ( n ) ). From the

above construction L ∈ NSPACE ( r ( n ) ). Thus, coNSPAC E ( r ( n ) ) ⊆ NSPACE ( r ( n ) ).

By similar reasoning, if L ∈ coNSPACE ( r ( n ) ), then L ∈ NSPACE ( r ( n ) ), which im-

plies that NSPACE ( r ( n ) ) ⊆ coNSPACE ( r ( n ) ); that is, they are equal.

The lowest class in the space hierarchy that is known to be closed under complements is
the class NL ;thatis, NL = coNL . This result is used in Section 8.11 to show that the problem
2- SAT , a specialization of the NP -complete problem 3- SAT ,isin P .
From Theorem 8.6.1 we know that all deterministic time and space complexity classes are
closed under complements. From Corollary 8.6.2 we also know that all nondeterministic space
complexity classes with space Ω(log n ) are closed under complements. However, we do not
yet know whether the nondeterministic time complexity classes are closed under complements.