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.