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

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 :
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
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
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 =
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
Previous Page Next Page