The Role of Theory in Computer Science - Models of Computation: Exploring the Power of Computing - page 27

into a string y of L 0 using an algorithm whose running time is a polynomial in the length
of x such that y is in L 0 if and only if x is in L . As a consequence of this definition, if any
NP -complete language can be solved in deterministic polynomial time, then every language in
NP can, including all the other NP -complete languages. However, the best algorithms known
today for NP -complete languages all have exponential running time. Thus, for long strings
these algorithms are impractical. If solutions to large NP -complete languages are needed, we
are limited to approximate solutions.

1.5.4 Circuit Complexity
Circuit complexity is a notoriously difficult subject. Despite decades of research, we have
failed to find methods to show that individual functions have super-polynomial circuit size
or more than poly-logarithmic depth. Nonetheless, the circuit is such a simple and appealing
model that it continues to attract a considerable amount of attention. Some very interesting
exponential lower bounds on circuit size have been derived when the circuits are monotone,
that is, realized by AND and OR gates but no NOT s.

1.6 Parallel Computation
The VLSI machine and the PRAM are examples of parallel machines. The VLSI machine
reflects constraints that exist when finite-state machines are realized through the very large-
scale integration of components on semiconductor chips. In the VLSI model the area of a chip
is important because large chips have a much higher probability of containing a disabling defect
than smaller ones. Consequently, the absolute size of chips is limited. However, the width of
lines that can be drawn on chips has been shrinking over time, thereby increasing the number
of wires, gates, and binary memory cells that can be placed on them. This has the effect of
increasing the effective chip area , the real chip area normalized by the cross section of wires.
Figure 1.11 (a) is a VLSI diagram representing the types of material that can be deposited on
the surface of a pure crystalline semiconductor substrate to form different types of conducting
regions. Some of the rectangular regions serve as wires whereas overlaps of other regions create
transistors. In turn, collections of transistors form gates. This VLSI diagram describes a NAND
gate, a gate whose Boolean function is the NOT of the AND of its two inputs. Shown in
Fig. 1.11 (b) is the logic symbol for the NAND gate. The small circle at the output of the AND
gate denotes the NOT ofthegatevalue.
Given the premium attached to chip real estate, a large number of economical and very
regular finite-state machine designs have been made for VLSI chips. One of the most im-
portant of these is the systolic array , a one- or two-dimensional array of processors (FSMs)
that are identical, except possibly for those along the periphery of the array. These processors
operate in synchrony; that is, they perform the same operation at the same time. They also
communicate only with their nearest neighbors. (The word “systolic” is derived from “systole,”
a “rhythmically recurrent contraction” such as that of the heart.)
Systolic arrays are typically used to compute specific functions such as the convolution
c = a

b of the n -tuple a =( a 0 , a 1 , ... , a n− 1 ) with the m -tuple b =( b 0 , b 1 , ... , b m− 1 ) .
The j th component, c j , of the convolution c = a

⊗

⊗ b ,0 ≤ j ≤ ( n + m −

2 ) ,isdefinedas

c j =
r + s = j

a r ∗ b s