24 1. Classical Computation

[1] 2.4. Let C be an O(log n)-depth circuit which computes some function

f :

Bn

→

Bm.

Prove that after eliminating all extra variables and gates in

C (those which are not connected to the output), we get a circuit of size

poly(n + m).

[1!] 2.5. Let C be a circuit (over some basis B) which computes a function

f :

Bn

→ B. Prove that C can be converted into an equivalent (i.e., comput-

ing the same function) formula C of the same depth over the same basis.

(It follows from the solution that the size of C does not exceed

cd,

where d

is the depth and c is the maximal fan-in.)

[3] 2.6 (“Balanced formula”). Let C be a formula of size L over the basis

{NOT, OR, AND} (with fan-in ≤ 2). Prove that it can be converted into an

equivalent formula of depth O(log L) over the same basis.

(Therefore, it does not matter whether we define the formula complexity

of a function in terms of size or in terms of depth. This is not true for the

circuit complexity.)

[1] 2.7. Show that any function can be computed by a circuit of depth ≤ 3

with gates of type NOT, AND, and OR, if we allow AND- and OR-gates

with arbitrary fan-in and fan-out.

[2] 2.8. By definition, the function PARITY is the sum of n bits modulo 2.

Suppose it is computed by a circuit of depth 3 containing NOT-gates, AND-

gates and OR-gates with arbitrary fan-in. Show that the size of the circuit

is exponential (at least

cn

for some c 1 and for all n).

2.3.2. Basic algorithms.

[3!] 2.9. Comparison. Construct a circuit of size O(n) and depth O(log n)

that tells whether two n-bit integers are equal and if they are not, which

one is greater.

[2] 2.10. Let n =

2l.

Construct circuits of size O(n) and depth O(log n)

for the solution of the following problems.

a) Access by index. Given an n-bit string x = x0 · · · xn−1 (a table)

and an l-bit number j (an index), find xj.

b) Search. Evaluate the disjunction y = x0 ∨· · ·∨xn−1, and if it equals

1, find the smallest j such that xj = 1.

We now describe one rather general method of parallelizing computation.

A finite-state automaton is a device with an input alphabet A , an output

alphabet A , a set of states Q and a transition function D : Q×A → Q×A

(recall that such a device is a part of a Turing machine). It is initially set

to some state q0 ∈ Q. Then it receives input symbols x0,...,xm−1 ∈ A and