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

In the above discussion we examine functions computed by Turing machines. If these

functions are characteristic functions , f :

B ∗ →B

; that is, they have value 0 or 1, then
those strings for which f has value 1 define a language L f . Also, associated with each language
L ⊆B ∗ is a characteristic function f L : B ∗ →B

that has value 1 on only those strings in L .

⊆B ∗ .Foreach n

Consider now a language L

≥

1 a circuit can be constructed whose

n and 0 otherwise. Similarly, given a family

value is 1 on binary strings in L

∩B C

of circuits

such that for each natural number n 1the n th circuit, C n , computes a Boolean function

on n inputs, the language L associated with this circuit family contains only those strings of
length n for which C n has value 1. We say that L is recognized by

≥

C

. At the risk of confusion,
we use the same name for a circuit family and the languages they define.
In Theorem 8.5.6 we show that NSPACE ( r ( n ))

TIME ( k log n + r ( n ) ) .Wenowuse
the ideas of that proof together with the parallel algorithm for transitive closure given in Sec-
tion 6.4 to show that languages in NSPACE ( r ( n )) , r ( n )

⊆

log n , are recognized by a uniform
family of circuits in which the n th circuit has size O ( k log n + r ( n ) ) and depth O ( r 2 ( n )) .When
r ( n )= O (log n ) , the circuit family in question is contained in the class NC 2 introduced in
the next section.

≥

THEOREM 8.13.3 If ⊆B ∗ is in NSPACE ( r ( n )) , r ( n ) log n , there exists a time-

r ( n ) uniform family of circuits recognizing L such that the n th circuit has size O ( k log n + r ( n ) )
and depth O ( r 2 ( n )) for some constant k .
Proof We assume without loss of generality that the NDTM accepting L has one accepting
configuration. We then construct the adjacency matrix for the configuration graph of M .
This matrix has a 1 entry in row i , column j if there is a transition from the i th to the
j th configuration. All other entries are 0. From the analysis of Corollary 8.5.1 ,thisgraph
has O ( k log n + r ( n ) ) configurations. The initial configuration is determined by the word w
written initially on the tape of the NDTM accepting L . If the transitive closure of this
matrix has a 1 in the row and column corresponding to the initial and final configurations,
respectively, then the word w is accepted.
From Theorem 6.4.1 the transitive closure of a Boolean p

language L

≥

× p matrix A can be computed

by computing ( I + A ) q

for q

≥ p −

1. Thiscanbedonebysquaring As times for

s log 2 p . From this we conclude that the transitive closure can be computed by a circuit

of depth O (log 2 m ) ,where m is the number of configurations. Since m = O ( k log n + r ( n ) ) ,
we have the desired circuit size and depth bounds.
Aprogramtocomputethe d th power of an p

≥

p matrix A is shown in Fig. 8.20 .This
program can be converted to one that writes the description of a circuit for this purpose,
and both the original and converted programs can be realized in space O ( d log p ) .(See

×

trans( A , n , d , i , j )
if d = 0 then
return( a i , j )
else

return( k = 1 trans( A , n , d

− 1, i , k ) * trans( A , n , d − 1, k , j ))

Figure 8.20 A recursive program to compute the d th power of an n × n matrix A .