Information Technology Reference
In-Depth Information
In this section we set the stage for discussing the parallel computation thesis in a limited
way by showing that every log-space reduction (on a Turing machine) can be realized by a
CREW PRAM in time
O
log
2
n
with polynomially many processors. This implies that if a
P
-complete problem can be solved on a PRAM with polynomially many processors in poly-
logarithmic time, then so can every problem in
P
, an unlikely prospect.
LEMMA
8.14.3
Log-space transformations can be realized by CREW PRAMs with polynomially
many processors in time
O
(log
2
n
)
.
Proof
We use the CREW PRAM described in the proof of Lemma
8.14.2
. The processors
in this PRAM are then assigned to perform the matrix operations in the order required
for a parallel prefix computation. (See Section
2.6
.) If we assign
|
Q
(
n
)
|
2
processors per
matrix multiplication operation, each operation can be done in
O
(log
2
)=
O
(log
n
)
steps. Since the prefix computation has depth
O
(log
n
)
, the PRAM can perform the prefix
computation in time
O
(log
2
n
)
. The number of processors used is
p
(
n
)
|
Q
(
n
)
|
2
)
,which
is a polynomial in
n
. Concurrent reads and exclusive writes suffice for these operations.
·
O
(
|
Q
(
n
)
|
Since a log-space transformation can be realized in poly-logarithmic time with polynomi-
ally many processors on a CREW PRAM, if a CREW PRAM solves a
P
-complete problem in
poly-logarithmic time, we can compose such machines to form a CREW PRAM with poly-
logarithmic time and polynomially many processors to solve an arbitrary problem in
P
.
THEOREM
8.14.2
If a
P
-complete problem can be solved in poly-logarithmic time with polyno-
mially many processors on a CREW PRAM, then so can all problems in
P
and all problems in
P
are fully parallelizable.
8.15 Circuit Complexity Classes
In this section we introduce several important circuit complexity classes including
NC
,the
languages recognized by uniform families of circuits whose size and depth are polynomial and
poly-logarithmic in
n
, respectively, and
P/poly
, the largest set of languages
L
⊂B
∗
with the
property that
L
is recognized by a (non-uniform) circuit family of polynomial size. We also
derive relationships among these classes and previously defined classes.
8.15.1 Efficiently Parallelizable Languages
DEFINITION
8.15.1
The class
NC
k
contains those languages
L
recognized by a uniform family of
Boolean circuits of polynomial size and depth
O
(log
k
n
)
in
n
, the length of an input. The class
NC
is the union of the classes
NC
k
,
k
≥
1
;thatis,
NC
=
k≥
NC
k
1
In Section
8.14
we explored the connection between circuit size and depth and PRAM
time and number of processors and concluded that circuits having polynomial size and poly-
logarithmic depth compute the same languages as do PRAMs with a polynomial number of
processors and poly-logarithmic parallel time.
Search WWH ::
Custom Search