Information Technology Reference
In-Depth Information
w
i
,
j
z
j
d
j
y
i
∧
w
i
,
j
c
i
w
i
,
j
s
0
z
j
s
0
u
j
w
i
,
j
s
1
...
...
y
m−
1
y
i
y
0
f
(
μ
)
decode
...
...
y
0
∧
w
0,
j
y
2
∧
w
2,
j
y
i
∧
w
i
,
j
y
1
∧
w
1,
j
y
m−
1
∧
w
m−
1,
j
a
μ−
1
a
μ−
2
a
0
(a)
(b)
Figure 8.22
A circuit for the next-state and output function of the random-access memory.
The circuit in (a) computes the next values for components of memory words, whereas that in (b)
computes components of the output word. This circuit is modified to generate a circuit for the
PRAM.
LEMMA
8.14.2
Let
C
=(
C
1
,
C
2
,
...}
be a log-space uniform family of circuits. There exists a
CREW PRAM that computes in poly-logarithmic time and a polynomial number of processors the
function
f
:
B
∗
→B
∗
computed by
C
.
Proof
The CREW PRAM is given a string
w
on which to compute the function
f
.First
it computes the length
n
of
w
. Second it invokes the CREW PRAM described below to
simulate with a polynomial number of processors in poly-logarithmic time the log-space
DTM
M
that writes a description of the
n
th circuit,
C
(
M
,
n
)
. Finally we show that the
value of
C
(
M
,
n
)
can be evaluated from this description by a CREW PRAM in
O
(log
2
n
)
steps with polynomially many processors.
Let
M
be a three-tape DTM that realizes a log-space transformation. This DTM has
a read-only input tape, a work tape, and a write-only output tape. Given a string
w
on its
input tape, it provides on its output tape the result of the transformation. Since
M
uses
O
(log
n
)
cells on its work tape on inputs of length
n
, it can be modeled by a finite-state
machine with 2
O
(log
n
)
states. The circuit
C
(
M
,
n
)
described in Theorem
3.2.2
for the
simulation of the FSM
M
is constructed to simulate
M
on inputs of length
n
.Weshow
that
C
(
M
,
n
)
has size and depth that are polynomial and poly-logarithmic in
n
, respectively.
We then demonstrate that a CREW PRAM can simulate
C
(
M
,
n
)
(and write its output into
its common memory) in
O
(log
2
n
)
steps with a polynomial number of processors.
Search WWH ::
Custom Search