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

The class NC is considered to be the largest feasibly parallelizable class of languages. By fea-
sible we mean that the number of gates (equivalently processors) is no more than polynomial
in the length n of the input and by parallelizable we mean that circuit depth (equivalently
computation time) must be no more than poly-logarithmic in n . Feasibly parallelizable lan-
guages meet both requirements.
The prefix circuits introduced in Section 2.6 belong to NC 1 , as do circuits constructed
with prefix operations, such as binary addition and subtraction (see Section 2.7 )andthecir-
cuits for solutions of linear recurrences (see Problem 2.24 ). (Strictly speaking, these functions
are not predicates and do not define languages. However, comparisons between their values
and a threshold converts them to predicates. In this section we liberally mix functions and
predicates.) The class NC 1 also contains functions associated with integer multiplication and
division.
The fast Fourier transform (see Section 6.7.3 ) and merging networks (see Section 6.8 )can
both be realized by algebraic and combinatorial circuits of depth O (log n ) ,where n is the
number of circuit inputs. If the additions and multiplications of the FFT are done over a ring
of integers modulo m for some m ,theFFTcanberealizedbyacircuitofdepth O (log 2 n ) .If
the items to be merged are represented in binary, a comparison operator can be realized with
depth O (log n ) and merging can also be done with a circuit of depth O (log 2 n ) .Thus,both
problems are in NC 2 .
When matrices are defined over a field of characteristic zero, the inverse of invertible ma-
trices (see Section 6.5.5 ) can be computed by an algebraic circuit of depth O (log 2 n ) .Ifthe
matrix entries when represented as binary numbers have size n , the ring operations may be
realized in terms of binary addition and multiplication, and matrix inversion is in NC 3 .
Also, it follows from Theorem 8.13.3 that the n th circuit in the log-space uniform families
of circuits has polynomial size and depth O (log 2 n ) ; that is, it is contained in NC 2 .Also
contained in this set is the transitive closure of a Boolean matrix (see Section 6.4 ). Since the
circuits constructed in Chapter 3 to simulate finite-state machines as well as polynomial-time
Turing machines are log-space uniform (see Theorem 8.13.1 ), each of these circuit families is
in NC 2 .
We now relate these complexity classes to one another and to P .

THEOREM 8.15.1 For k ≥ 2 , NC 1 NC 2 NC k ⊆ ⊆ L ⊆ NL ⊆ ⊆ NC ⊆ P .

NC 2 is a restriction
of the result of Theorem 8.13.3 to r ( n )= O (log n ) . The containments NC 2

⊆ ⊆

Proof The containment L NL is obvious. The containment NL

NC k ⊆ ⊆

NC follow from the definitions. The last containment, NC P , is a consequence of the

fact that the circuit on n inputs in a log-space uniform family of circuits, call it C n ,can
be generated in polynomial time by a Turing machine that can then evaluate C n in a time
quadratic in its length, that is, in polynomial time. (Theorems 8.5.8 and 8.13.2 apply.)
The first containment, namely NC 1

⊆

⊆ L , is slightly more difficult to establish. Given a

NC 1 , consider the problem of recognizing whether or not a string w is in L .
This recognition task is done in log-space by invoking two log-space transformations, as is
now explained.
The first log-space transformation generates the n th circuit, C n , in the family recogniz-
ing L . C n has value 1 if w is in L and 0 otherwise. By definition, C n has size polynomial
in n . Also, each circuit is described by a straight-line program, as explained in Section 2.2 .

language L ∈