Boolean Circuit Complexity Fall Semester, 1994-5

Lecture 3: November 10

Lecturer: Uri Zwick Scribe: Rani Nelken

3.1 Simulation of Turing Machines by Circuits

Theorem 3.1 (Pippenger, Fischer 1979), (Schnorr 1976) Let M be a Turing Machine (TM) having a finite number of (one-dimensional) tapes. For every n ≥ 0, the machine defines a Boolean function: f_{M,n} : {0, 1}^{n} → {0, 1}, in the natural manner^{1}. Let T (n) be a bound on the number of steps, that M executes on inputs of length n. There exists a series of circuits: C_{1}, C_{2}, … that computes the functions: f_{M,1}, f_{M,2}, … such that the size of the n^{th} circuit is O(T (n) log T (n)).

As a simple corollary from theorem 3.1, if we can prove a lower bound of ω(n log n) on the size of circuits, needed for the computation of a certain function (actually, a family of functions - a different one for each input length), we will have a non-linear lower bound on the time needed for the computation of the function by a TM, with any number of one-dimensional tapes.

We will not prove Theorem 3.1 here. Instead, we show a weaker bound of O(T^{2}(n)), or actually O(T (n)S(n)), where S(n) is a bound on the space complexity of the TM. The proof is given only for the case in which, the machine has a single tape. Generalizing it to any number of tapes is not difficult.

Proof: Let M be a quintuple M = (Σ, Q, q_{0}, q_{1}, δ), where

• Σ is a finite alphabet

• Q is a finite set of states

• q_{0} ∈ Q is the initial state

• q_{1} ∈ Q is the accepting state

• δ : Q × Σ ⟶ Q × Σ × {L, R} is the transition function.

Each state in Q will be represented by ⌈log |Q|⌉ bits, and each letter of Σ by ⌈log |Σ|⌉ bits. Using this representation, δ can be seen as a Boolean function of a constant number of bits, and may be implemented by a circuit of constant size, as shown in Figure 3.1, which is labeled δ.

1The function f_{M,n} maps each string over {0, 1}^{n} accepted by M to 1 and all the rest to 0.

[figure: δ; q ∈ Q; a ∈ Σ; a′; q′; 1 iff the head; should move; to the right; 1 iff the head; should move; to the left]

Figure 3.1: The circuit δ

The circuit δ is a basic building block in a circuit that simulates M. Let x_{1} x_{2} …, x_{n} be binary variables representing the first n binary digits in the representation of the input written on the tape of M, before it starts executing. The circuit simulating M will receive as input the variables x_{i}, and compute the function calculated by M. It will have T (n) different layers, one for each time unit 0 ≤ t ≤ T (n). The binary values at each layer of the circuit encode a ‘configuration’ of the machine (its state, tape content, and the location of its head). It is clearly sufficient to include in such a configuration, the content of the tape cells −T (n) ≤ i ≤ T (n) only. For each point of time, 0 ≤ t ≤ T (n), for every cell of the tape −T (n) ≤ i ≤ T (n), we keep a binary array, shown in Figure 3.2.

[figure: is the head; at cell i at; time t; If so, what is; the state ?; what letter is; written at cell i ?]

Figure 3.2: The binary array

The circuit computes these arrays, according to the following layers:

First layer: For t = 0, these arrays are composed of the variables x_{1} x_{2} …, x_{n}, and constants.

Intermediate layers: Given the arrays for some time t, the arrays for time t + 1, are constructed in parallel, using γ circuits, similar to δ (see Figure 3.3).

Each γ circuit gets as input one of the arrays of time t, and creates, at its output, the corresponding array of time t + 1. If the head is in the cell, for which the γ circuit is ‘responsible’, the array is changed according to δ, and the appropriate neighboring γ circuit is notified of the head movement. This neighbor then updates its array accordingly. All other γ circuits output their input array, without change.

A difference between the original transition function of M, and the circuit γ, is that once M reaches q_{1}, the accepting state, it halts. The circuit, on the other hand, cannot stop, so when a γ circuit gets as input an array, in which the encoded state is q_{1}, the array is left unchanged, and the head is not moved.

Last layer: The last layer in the construction is a circuit, that checks whether the state, encoded at the array where the head bit is 1, is q_{1}.

The size of the circuit, thus constructed, is O(T^{2}(n)). It is interesting, that its depth is O(T (n)), the same as M’s time complexity. □

γ  γ  γ ⟹ ⟸ 0  1  0 The new letter ⟹ ⟸

Figure 3.3: A circuit to simulate M

Most of the complexity in the above construction arises from dealing with the movement of the head, which may depend on the input. A simpler circuit may be constructed for so-called oblivious TM’s:

Definition A Turing Machine will be called oblivious iff the location of the head at time t does not depend on the input.

Using the ideas used above, we get:

Claim 3.2 An oblivious TM, M, with time complexity T (n), can be simulated by a series of circuits of size O(T (n)).

At first sight, obliviousness may seem a rather severe restriction on TM’s, but by using a back-and-forth serpentine motion (see Figure 3.4), every TM with time complexity T (n) can be simulated by an oblivious TM, with time complexity O(T^{2}(n)). This gives an alternative proof of the O(T^{2}(n)) bound on the size of circuits that simulate TM’s: given a TM, we construct an equivalent oblivious TM, which is then simulated by a series of circuits. Pippenger and Fischer managed to improve this result to O(T (n) log T (n)), quoted here as Theorem 3.1.

−t  head  t

Figure 3.4: Simulating a TM with an oblivious TM

3.2 Basic arithmetic operations

In this section, we discuss the implementation of basic arithmetic operations, addition and multiplication, by circuits.

3.2.1 Addition

Input: two n-bit numbers. Output: one n + 1-bit number, which is their sum.

x_{n−1} x_{n−2} … x_{1} x_{0}
+ y_{n−1} y_{n−2} … y_{1} y_{0}
z_{n} z_{n−1} z_{n−2} … z_{1} z_{0}

We discuss the following methods for computing addition:

1. The naive method also known as Carry-ripple addition

2. Carry-look-ahead addition

Carry-ripple addition

The ordinary way of adding two n-bit binary numbers uses the carry bit, in computing the sum. For each two bits x_{i}, y_{i}, the sum bit and carry-out bit are computed, based on x_{i}, y_{i}, and the carry-in bit c_{i}. A component, called full-adder or FA, shown in Figure 3.5, performs this computation, and may serve as the basic building block in a circuit which computes the sum of n-bit numbers, as shown in Figure 3.6. The carry bit ‘ripples’ along the cascade of FA’s. Notice that c_{0}, the carry-in bit for the first FA is 0, and that c_{n}, the carry-out bit of the last FA is used as z_{n}, the n + 1^{th} bit of the output.

[figure: c; y; x; Maj(x, y, c); FA; x ⊕ y ⊕ c]

Figure 3.5: A Full Adder

FA FA  FA  0 c_{1} c_{2}  x_{0} y_{0} z_{0} z_{1} z_{n−1}  c_{n−1} x_{n−1} y_{n−1}  x_{1} y_{1} … z_{n}

Figure 3.6: Structure of a Carry-ripple adder

The functions used in the implementation of a full-adder are shown in Figure 3.5. The sum-bit is the XOR of the input and carry-in bits. The carry-out is the majority of these three bits. There are several ways of implementing the majority function:

Maj(x, y, c) = xy ∨ xc ∨ yc = xy ∨ (x ∨ y)c = xy ∨ (x ⊕ y)c =
= xy ⊕ (x ⊕ y)c = (x ⊕ c)(y ⊕ c) ⊕ c

The first of these expressions is the DNF of the majority function. The next four expressions include five occurrences of variables, two occurrences each of x and y, and one occurrence of c, all except the last expression, which contains just one occurrence of x and y each, and three occurrences of c. For reasons, that may become apparent in a subsequent lecture, this last expression is the most efficient for implementation by formulas. An efficient circuit implementing an FA, using 5 gates, is shown in Figure 3.7. Since the first carry-in bit is always 0, the first FA can be replaced by a half adder or HA, which uses only two gates (see Figure 3.8), thus proving the following corollary:

Sum Carry  z⊕ ⊕ ∧ ∨  y x  ∧

Figure 3.7: An efficient implementation of a full adder

Corollary 3.3 C_{B_{2}}(ADD_{n}) ≤ 5n − 3

At this point, it is natural to ask, whether this is the optimal size of an FA, or of a circuit implementing ADD_{n}. The answer is given by the following theorem^{2}:

2This result is not an improvement on Blum’s 3n lower bound on the size of circuits needed to implement

[figure: HA; x; y; x ⊕ y; x ∧ y]

Figure 3.8: A Half Adder

Theorem 3.4 (Red’kin) C_{B_{2}}(ADD_{n}) = 5n − 3

Thus, the Carry-ripple adder achieves optimal size, but its depth is terrible: 2n − 1. We will seek a construction of an ADD_{n} circuit of size O(n) and depth O(log n).

Carry-look-ahead adders

We define two variables g, which stands for carry generate, and p, which stands for carry propagate in the following way:

p_{i} = x_{i} ∨ y_{i}
g_{i} = x_{i} ∧ y_{i}

For a given FA_{i}, we set c_{out} = 1 if g_{i} = 1, and c_{out} = c_{in} if p_{i} = 1. From these definitions, it is easy to verify that:

c_{i+1} = g_{i} ∨ p_{i}c_{i} = … = ⋁_{j=0}^{i}(g_{j} ∧ ⋀_{k=j+1}^{i} p_{k})

Where

⋀_{k=i+1}^{i} p_{k}

is defined to be 1, and c_{0} = 0. The i^{th} output bit, z_{i}, is defined as z_{i} = x_{i} ⊕ y_{i} ⊕ c_{i}. Once the carry bits are computed, it is a simple matter to compute the output bits z_{i}. In the formula for c_{i+1}, the conjunction contains at most n elements, and may thus be computed in log n depth. The next level in the construction is the disjunction, which contains at most n such conjunctions, adding another factor of log n, to the depth of the circuit. The total depth is thus 2 log n. Using this formula, c_{i} can be computed by a U_{2}-circuit of depth ≈ 2 log n, and size O(n^{2}).

a function, given in the previous lecture. Blum’s bound holds for functions f : {0, 1}^{n} → {0, 1}, whereas ADD_{n} : {0, 1}^{2n} → {0, 1}^{n+1}.

This computation has to be done for each c_{i}. The most naive way to do this, is by separately computing each c_{i}, with a different circuit. The total size of such a construction is O(n^{3}). We have thus gained in depth, but lost in size. We can actually do better than this, as shown by the following two theorems:

Theorem 3.5 (Brent, Khrapchenko) ADD_{n} can be implemented by a U_{2}-circuit of depth log n + O(\sqrt{log n}) and size O(n).

Theorem 3.6 (Chandra, Fortune, Lipton) For any primitive recursive function f(n), it is possible to construct a U_{∞}-circuit of constant depth and O(nf^{−1}(n)) edges^{3}, i.e., an almost linear number of edges.

From Theorem 3.6, we conclude that it is possible to construct a U_{∞}-circuit, that computes ADD_{n}, with e.g., O(n log^{∗} n) edges. However, it is unclear, whether it is possible to use α, the inverse of Ackermann’s function as f^{−1}, since Ackermann’s function is not primitive recursive.

Theorem 3.7 (Dolev, Dwork, Pippenger and Wigderson) There is no U_{∞}-circuit which implements ADD_{n} with constant depth and O(n) edges.

We will prove a weaker version of theorem 3.5, by constructing ADD_{n} circuits of depth O(log n) and size O(n), using the Prefix Sums method. We define:

D = {C, P, G}
∘ : D × D → D

Where C stands for clear, P for propagate and G for generate. The operation ∘ is defined by the following matrix:

C P G C P G C C C C P G G G G

3By counting the number of edges over U_{∞}, it is as if we are counting the number of wires of a digital circuit, thus although we allow U_{∞}-gates, a gate with more inputs costs more.

It is easy to verify that ∘ is associative. For each 0 ≤ i ≤ n, we can assign a value d_{i} ∈ D, based solely on x_{i} and y_{i} (similarly to the way the functions p_{i} and g_{i} were defined above). We set c_{i+1} = 1 iff d_{i} ∘ d_{i−1} ∘ ⋯ d_{0} = G.

Abstracting away from the problem of computing ADD_{n}, we construct a circuit that, given a series of inputs x_{1}, x_{2}, … x_{n}, computes x_{1}, x_{1} ∘ x_{2}, x_{1} ∘ x_{2} ∘ ⋯ x_{n}, in O(n) size and depth exactly log n, using ∘ gates, for any associative operation ∘. For the implementation of ADD_{n}, ∘ gates are simulated, using gates of the bases Ω, that we are working with. Note, that Theorem 3.5 holds over U_{2}, since the ‘hard’ part in the computation of ADD_{n} is the computation of the carry bits, and the contribution of the gates for computing the Maj function (for which ⊕ gates would be helpful) is negligible.

For the sake of simplicity we assume n = 2^{k}, other cases can be dealt with similarly. We show two different recursive constructions:

1. We construct P (n), a circuit that computes all the prefix operations of x_{1} ∘ x_{2} ∘ ⋯ x_{n}, thus:

• P (1) is trivial

• P (2) is shown in Figure 3.9

P (2) x_{1}  x_{2} x_{1}  x_{1} ∘ x_{2} Figure 3.9: P(2)

• Given P (\frac{n}{2}), P (n) is constructed, as shown in Figure 3.10.

Let C(n) be the size of the circuit P (n) using ∘ gates, and D(n), its depth. We get the following recurrences:

C(n) = C(\frac{n}{2}) + n − 1 C(2) = 1

D(n) = D(\frac{n}{2}) + 2 D(2) = 1

x_{1}  x_{2}  x_{3}  x_{4}  … P (\frac{n}{2})  x_{n−1}  x_{n} x_{1}x_{1} ∘ x_{2}  x_{1} ∘ x_{2} ∘ x_{3} ∘ x_{4} x_{1} ∘ x_{2} ∘ x_{3}  x_{1} ∘ x_{2} ∘ ⋯ ∘ x_{n} … Figure 3.10: P (n)

Solving this:

C(n) = 2n − (log n + 2)
D(n) = 2 log n − 1

2. It is possible to improve on the construction above, reducing the 2 log n depth to log n. The circuits we present were obtained by Ladner and Fischer. This is done by two sequences of circuits: P_{0}(n) - a circuit of depth log n (exactly) P_{1}(n) - a circuit of depth ≤ log n + 1, but where the (last) output, x_{1} ∘ x_{2} ∘ ⋯ x_{n}, is computed at depth log n. The construction is as follows:

• P_{0}(2) = P_{1}(2) = P (2)

• Given P_{0}(\frac{n}{2}) and P_{1}(\frac{n}{2}), we construct P_{0}(n) and P_{1}(n) as shown in Figure 3.11 and Figure 3.12, respectively. We have already seen the depth of these circuits, so we are left with the calculation of their sizes. Defining C_{0}(n) and C_{1}(n) to be the sizes of the circuits P_{0}(n) and P_{1}(n), respectively, we get the following recurrences:

C_{0}(n) = C_{0}(\frac{n}{2}) + C_{1}(\frac{n}{2}) + \frac{n}{2}

C_{1}(n) = C_{0}(\frac{n}{2}) + n − 1

log \frac{n}{2} + 1 = log n  P_{0}(\frac{n}{2}) P_{1}(\frac{n}{2}) x_{1} x_{2}  x\frac{n}{2}  x_{\frac{n}{2} +1}  x_{n} x_{1}  x_{1} ∘ x_{2} ∘ ⋯ ∘ x\frac{n}{2}  x_{1} ∘ x_{2} ∘ ⋯ ∘ x_{n} log n − 1

Figure 3.11: P_{0}(n)

x_{1} x_{2}  x_{3}  x_{4}  …  x_{n−1}  x_{n} x_{1}x_{1} ∘ x_{2}  x_{1} ∘ x_{2} ∘ x_{3} ∘ x_{4} x_{1} ∘ x_{2} ∘ x_{3}  x_{1} ∘ x_{2} ∘ ⋯ ∘ x_{n} … P_{0}(\frac{n}{2})  log n − 1 log n + 1

Figure 3.12: P_{1}(n)

Solving this, yields C_{0}(n) = 4n − F_{log n+5} + 1 = 4n − o(n), where F_{k} is the k^{th} Fibonacci number. F_{k} ≈ ϕ^{k} ≈ 1.6^{k}. Thus, F_{log n+5} = o(n). C_{1}(n) = 3n −

F_{log n+4} = 3n − o(n).

There are further optimizations on these methods. For instance, the multiplicative factor of 4 in the expression for C_{0}(n) can be reduced to ≈ 2.5, if instead of using P_{1}, with a ‘delay’ of 1 in the last output, we construct a different circuit, P_{2}, with depth log n + 2.

3.2.2 Multiplication

In this section, we describe circuits for the computation of the multiplication of two n-bit binary numbers. The naive (or grade-school) method for multiplying two n-bit numbers takes size O(n^{2}) and depth O(log^{2} n):

x_{n−1} … x_{1} x_{0}
× y_{n−1} … y_{1} y_{0}
x_{n−1}y_{0} … x_{1}y_{0} x_{0}y_{0}
x_{n−1}y_{1} … x_{1}y_{1} x_{0}y_{1}
⋮
x_{n−1}y_{n−1} … x_{1}y_{n−1} x_{0}y_{n−1}
z_{2n−1} z_{2n−2}  …  z_{0}

Reducing the circuit size - Karatsuba’s method

The circuit size can be improved by using Karatsuba’s method of size reduction. Given two n-bit numbers x and y, we split them down the middle. Not all four multiplications have to be done:

x_{1}  \underbrace{x_{0}}_{\frac{n}{2}}

×  y_{1}  y_{0}
x_{1}y_{1}  \underbrace{x_{0}y_{0}}_{n}
+  x_{1}y_{0} + x_{0}y_{1}

Since we are interested only in the sum, we do not have to separately calculate x_{0}y_{1} and x_{1}y_{0}. Instead, we calculate the sum x_{0}y_{1} + x_{1}y_{0}, by using the formula^{4}:

x_{0}y_{1} + x_{1}y_{0} = (x_{0} + x_{1})(y_{0} + y_{1}) − x_{0}y_{0} − x_{1}y_{1}

Thus, just three multiplications are actually calculated:

• x_{0}y_{0}

• x_{1}y_{1}

• (x_{0} + x_{1})(y_{0} + y_{1})

In this way, the problem of multiplying two n-bit numbers reduces to three (not four) problems of multiplying \frac{n}{2}-bit (or \frac{n}{2} +1) numbers (plus some additions), yielding the following recurrence^{5}:

M(n) = 3M(\frac{n}{2}) + O(n)

Solving the recurrence, we get:

M(n) = O(n^{log_{2} 3}) ≈ n^{1.59}

The same idea can be used to implement the multiplication of two real numbers, using three real multiplications instead of four. Complex numbers may be multiplied in the same manner, splitting the numbers between the real and imaginary parts. This method is actually used in the implementation of symbolic computations on large numbers. An improvement on this method splits the numbers, not to two, but to k parts, e.g., if each number is split into three, we do not need all the 9 multiplications, more than a quarter of these may be saved. In this way, for each ϵ > 0, a multiplication circuit of size O(n^{1+ϵ}) can be constructed.

The Fast Fourier Transform

The most efficient method known, of computing multiplication is by using the FFT:

Theorem 3.8 (Schönhage, Strassen) There exist multiplication circuits of size O(n log n log log n) and depth O(log n), using the FFT.

4Subtraction is implemented as addition in 2’s complement.

5Actually, the right side of the recurrence should contain 3M(\frac{n}{2} + 1) and not 3M(\frac{n}{2}), but the difference can be ‘swallowed’ in the O(n) term.

The regular FFT algorithm works on polynomials and takes time O(n log n). The additional factor of log log n in the size of the circuits in Theorem 3.8 is due to the translation of numbers into polynomials. Note, that polynomials do not have a ‘carry’. Also, FFT is usually calculated over the complex numbers, which may result in round-off errors, which are unacceptable here. It is possible to overcome this, by computing the FFT over a ring Z_{m} of integers modulo some large number m. Multiplication of the pointwise values, in the ring, can be done efficiently, either by recursively using the FFT, or by using the grade school method.

There is no known non-linear lower bound on the circuit size of multiplication. Thus, whereas in the case of addition, almost everything is known, in the case of multiplication, the picture is yet incomplete. We close this section with an implementation of multiplication, which uses depth O(log n).

Multiplication using Carry-Save adders

The grade-school method called for the summation of n numbers - partial products obtained from multiplying the n-bit number x by the bit y_{i}. Computing each of these partial products is trivial. Thus, an efficient circuit for the summation of n numbers of length n—2n bits, could be used as a component of an efficient multiplication circuit. The naive solution for the summation problem uses depth O(log^{2} n), but the depth can be reduced to O(log n), using Carry-Save adders (CSAs). A CSA takes as input, three numbers, and gives as output, two numbers, the sum of which is equal to the sum of the three inputs, depicted graphically in Figure 3.13.

Figure 3.13: The function of a 3 → 2 - CSA

A CSA, which transforms three numbers into two (which we label 3 → 2), in O(1) depth, is shown in Figure 3.14. Note, that we can view the two numbers at the output of a CSA as a redundant representation of the sum of the three inputs, using three digits: 0, 1 and 2 (written in binary).

Based on the 3 → 2-CSA, we can construct a n → 2 summation circuit, by building a directed acyclic graph with ≈ log_{\frac{3}{2}} n layers of 3 → 2-CSA’s, as shown in Figure 3.15. The output of this circuit is a pair of numbers, which are added, using a Carry-Look-ahead adder.

… 0  y_{0} = 0 x_{0} y_{1} x_{1} y_{2}  FA FA FA

Figure 3.14: A 3 → 2-CSA

CSA  CSA  CSA CSA  CSA CSA CSA

Figure 3.15: n → 2-CSA