2. Boolean circuits 25
changes its state from q0 to q1 to q2, etc., according to the
rule2
(qj+1,yj) = D(qj,xj).
The iterated application of D defines a function
Dm
: (q0,x0,...,xm−1)
(qm,y0,...,ym−1). We may assume without loss of generality that Q =
Br,
A =
Br
, A =
Br
; then D :
Br+r

Br+r
whereas
Dm
:
Br+r m

Br+r m.
The work of the automaton can be represented by this diagram:
xm−1 x1 x0

qm

D
q
✛m−1
· · ·
✛q2
D
✛q1
D

q0

ym−1 y1 y0
[3!] 2.11 (“Parallelization of iteration”). Let the integers r, r , r and m be
fixed; set k = r + r + r . Construct a circuit of size exp(O(k)) m and depth
O(k log m) that receives a transition function D :
Br+r

Br+r
(as a value
table), an initial state q0 and input symbols x0,...,xm−1, and produces the
output (qm,y0,...,ym−1) =
Dm(q0,x0,...,xm−1).
[2!] 2.12. Addition. Construct a circuit of size O(n) and depth O(log n)
that adds two n-bit integers.
[3!] 2.13. The following two problems are closely related.
a) Iterated addition. Construct a circuit of size O(nm) and depth
O(log n + log m) for the addition of m n-digit numbers.
b) Multiplication. Construct a circuit with the same parameters for
the multiplication of an n-digit number by an m-digit number.
[3!] 2.14. Division. This problem also comes in two variants.
a) Compute the inverse of a real number x=1.x1x2 · · · =1+
∑∞
j=1
2−jxj
with precision
2−n.
By definition, this requires to find a number z such that
|z
x−1|

2−n.
For this to be possible, x must be known with precision
2−n
or better; let us assume that x is represented by an n + 1-digit number
x such that |x x|
2−(n+1).
Construct an
O(n2
log n)-size, O((log
n)2)-
depth circuit for the solution of this problem.
2Our definition of an automaton is not standard. We require that the automaton reads and
outputs one symbol at each step. Traditionally, an automaton is allowed to either read a symbol,
or output a symbol, or both, depending on the current state. The operation of such a general
automaton can be represented as the application of an automaton in our sense (with a suitable
output alphabet B) followed by substitution of a word for each output symbol.
Previous Page Next Page