Boolean Circuit Complexity Fall Semester, 1994-5

Lecture 1: October 27

Lecturer: Uri Zwick Scribe: Omer Shibolet

1.1 Definitions

• A Boolean function is a function f : {0, 1}^{n} → {0, 1}.

• B_{n} is the set of all Boolean functions of n variables.

• A Basis Ω is a collection (finite or infinite) of Boolean functions.

• A circuit C over Ω is a directed acyclic graph in which every node v, with deg_{in}(v) = 0 (such a vertex v is called an input of the circuit) is labeled by a variable (x_{1}, x_{2}, …) or its negation, or a constant. Every other node u is called a gate and is labeled by a function from Ω of deg_{in}(u) variables. A special node w with deg_{out}(w) = 0 is defined to be the output of the circuit. A Boolean circuit computes a Boolean function in a natural way. Each node v of a circuit C computes a Boolean function res(v) in the following way: if v is an input then res(v) is the variable (or its negation) or the constant labeling v. If v is labeled by a function f and (u_{1}, v), …, (u_{deg_{in}(v)}, v) are the edges entering v then res(v) = f(res(u_{1}), …, res(u_{deg_{in}(v)})). This definition is legal since the underlying graph of C is acyclic. The function res(w), where w is the output gate of C, is the Boolean function computed by C.

• Functions with a variable number of inputs (e.g., decision functions for binary languages) can be computed using a sequence of circuits. Each circuit computes the function for a given number of inputs. As a different circuit is used for each number of inputs, the circuit model is a non uniform model.

• A basis Ω is complete iff all Boolean functions can be computed by circuits over Ω.

• The size of a circuit is the number of gates in it.

• The depth of a circuit is the length of the longest directed path in it.

• A Boolean function f is monotone iff x ≤ y implies f(x) ≤ f(y). By x ≤ y, when x and y are bit vectors, we mean that each bit of x is less than or equal to the corresponding bit in y (this is only a partial order).

2 Lecture 1: October 27 • A Boolean function f is said to be self-dual iff f(\overline{x}) = \overline{f(x)}, for every x in the domain.

• A Boolean function f is said to be affine iff f can be displayed in the form f(x) ≡ x_{i_{1}} ⊕ x_{i_{2}} ⊕ ⋯ ⊕ x_{i_{k}} ⊕ c , for some c ∈ {0, 1}

• We define a Boolean operator x^{a} , for a ∈ {0, 1}, as:

x^{a} = \{ \begin{matrix}x̄ & if a = 0 \\ x & if a = 1 \end{matrix}

If ∧ and ∨ (and, or) functions with unlimited number of arguments are allowed, with possibly a negation on each argument, then any Boolean function can be computed by a circuit of depth 2 - the Boolean function is converted into its DNF, and then implemented as shown in Figure 1.1.

…  ^{…}^{…}^{and}  ^{and}^{and}  OR

Figure 1.1: A DNF formula can be implemented in depth 2

Also note, that the size of such circuit, given only two input gates is ≤ n · 2^{n}

1.2 The bases over functions of 2 arguments

The functions f : {0, 1}^{2} → {0, 1} of two Boolean variables can be classified as following : • 0, 1 - constant functions (2 functions).

• x^{a}, y^{a} where a ∈ {0, 1} - functions of one significant variable (4 functions).

1.3. CHARACTERIZING THE COMPLETENESS OF BASES 3 • (x ⊕ y)^{a} where a ∈ {0, 1} - affine functions of two significant variables (2 functions).

• (x^{a} ∧ y^{b})^{c} where a, b, c ∈ {0, 1} - the non-affine functions (8 functions).

We specify two special bases of two variable functions:

1. U_{2} = {(x^{a} ∧ y^{b})^{c} : a, b, c ∈ {0, 1}}

2. B_{2} = {all the functions of 2 variables }

1.3 Characterizing the completeness of bases

The following theorem is due to Post (1941). Theorem 1.1 A basis Ω is complete iff :

1. There exists f ∈ Ω such that f(0, 0, …, 0) = 1.

2. There exists f ∈ Ω such that f(1, 1, …, 1) = 0.

3. There exists f ∈ Ω which in not monotone.

4. There exists f ∈ Ω which in not self-dual.

5. There exists f ∈ Ω which in not affine. Proof: One direction is trivial. We prove the other - that if the five conditions hold, then Ω is complete:

1. There exists f_{1} ∈ Ω such that f_{1}(0, 0, …, 0) = 1, and therefore either f_{1}(x, x, …, x) ≡ 1 (f is constant) or f_{1}(x, x, …, x) ≡ \overline{x}.

2. In a similar way, there exists f_{2} ∈ Ω such that either f_{2}(x, x, …, x) ≡ 0 or f_{2}(x, x, …, x) ≡ \overline{x}.

Now there are three possibilities for the set {f_{1}, f_{2}}:

(a) One of the functions is \overline{x} and the other a constant (0 or 1). In this case, by negating we have all of \{\overline{x}, 0, 1\}.

(b) The functions f_{1} and f_{2} are the two different constant functions, 0 and 1, or (c) Both f_{1}, f_{2} ≡ \overline{x}.

3. There exists f_{3} ∈ Ω, f_{3} is non-monotone.

Claim 1.2 There exist constants α_{1}, …, α_{n} such that f_{3}(α_{1}, …, 0, …, α_{n}) = 1 and f_{3}(α_{1}, …, 1, …, α_{n}) = 0.

Proof: Since f_{3} is non-monotone, there are x ≤ x′ such that f_{3}(x) > f_{3}(x′). Let us assume the claim is wrong, and look at the indices I = {i|x_{i} < xi^{′}} (I is not empty). Starting from y = x, f_{3}(y) = 1, we change the indices I in y from 1 to 0, one at a time, and examine the current value of f_{3}(y). Since we assume the claim does not hold, at each change of bit in y, f_{3}(y) = 1. Therefore, at the end of the process, when y = x′, we still have f_{3}(y) = f_{3}(x′) = 1, a contradiction. Observe that by now we can surely implement the complement function - If f_{1}, f_{2} were constants, we can use f_{3}(α_{1}, …, x, …, α_{n}) ≡ \overline{x}.

4. There exists f_{4} ∈ Ω which is not self-dual. So there exists a vector α such that f_{4}(\overline{α}) = f_{4}(α), and therefore f_{4}(x^{α_{1}}, x^{α_{2}}, …, x^{α_{n}}) ≡ c , a constant function. Observe that by using f_{4} and the complement function, we can get the complementary constant, and by thus both the constants 0 and 1.

5. There exists f_{5} ∈ Ω which is not affine. Our objective here is to get a function h of

the form

h = (x^{a} ∧ y^{b})^{c}  (1.1)

for some a, b, c ∈ {0, 1}. Suppose we can implement h = (x^{a} ∧ y^{b})^{c}, then implementing ∧, e.g., is easy : Use a composition of h and the negation function, which we already have. Compose h = [[(x^{a})^{a} ∧ (y^{b})^{b}]^{c}]^{c}, and it is easy to see that since (w^{a})^{a} = w, for a ∈ {0, 1}, we get h ≡ x ∧ y. Together with the negation function, we then have a complete basis {∧, ¬}.

Without loss of generality, f_{5} can be displayed in the form

f_{5}(x_{1}, x_{2}, …, x_{k}) ≡ x_{1} · f5^{′}(x_{2}, …, x_{k}) ⊕ f5^{′′}(x_{2}, …, x_{k}).  (1.2)

For this purpose, take f5^{′′}(x_{2}, …, x_{k}) = f_{5}(0, x_{2}, …, x_{k}), and

f5^{′}(x_{2}, …, x_{k}) = f_{5}(1, x_{2}, …, x_{k}) ⊕ f_{5}(0, x_{2}, …, x_{k})), and Equation 1.2 holds.

We recursively continue this decomposition, starting from g_{0} = f_{5}, each time decomposing (by Equation 1.2) g_{i} = x · g′_{i} ⊕ g′′_{i}, and g_{i+1} = g′′_{i} , until one of the following happens:

(a) Either we get a non-affine function g_{j} of two variables. As the classification of functions of two variables shows, this g_{j} is the function we need for Formula 1.1 and by thus the proof is completed, or

(b) We get an affine function g′′_{j}, such that g_{j} = x · g′_{j} ⊕ g′′_{j}.

1.4. THE COMPLEXITY MEASURES C_{Ω}, D_{Ω} 5

First observe, that g_{j} is non-affine (otherwise, we would have stopped earlier since g_{j} = g′′_{j−1}). Then note that g′_{j} ≢ 0, 1, because then g_{j} would have also been affine. For the construction of h as in Formula 1.1, we need the next claim:

Claim 1.3 There exists a vector α and constant a such that x^{a} ≡ g′_{j}(α_{1}, …, x, …, α_{l}).

Proof: Suppose the claim is false. We show that g′_{j} is a constant function, which leads to a contradiction. If g′_{j} is not constant, then there exist two vectors, α^{1} ≠ α^{2}, such that g′_{j}(α_{1}^{1}, …, α_{l}^{1}) ≠ g′_{j}(α_{1}^{2}, …, α_{l}^{2}). Change α^{1} into α^{2}, switching one bit at a time. By negating the claim, we get that for every j ∈ [1..l], and for every vector α, g′_{j}(α_{1}, …, α_{j}, …, α_{l}) = g′_{j}(α_{1}, …, ᾱ_{j}, …, α_{l}). So every switch of a single bit in α^{1} does not change g′_{j}(α^{1}), therefore after switching all the necessary bits in α^{1} into the value of α^{2}, we still have g′_{j}(α^{1}) = g′_{j}(α^{2}), a contradiction.

Now, let us look at g_{k}(α_{1}, …, x, …, α_{l}) = x · y^{a} ⊕ \underbrace{g′′(α_{2}, …, y, …, α_{l})}_{0,1,y,\overline{y}}.

It is easy to check that in any of the four possibilities (g′′(α_{2}, …, y, …, α_{l}) ≡ \{0, 1, y, \overline{y}\}) we have g_{k}(α_{1}, …, x, …, α_{l}) = (x^{a} ∧ y^{b})^{c}, a, b, c ∈ {0, 1}, and this is an implementation of the function h from Formula 1.1, thus concluding the proof.

1.4 The complexity measures C_{Ω}, D_{Ω}

1.4.1 Definitions and basic properties

• C_{Ω}(f), the circuit complexity of f with respect to a basis Ω, is the minimum size of a circuit over Ω that computes f.

• D_{Ω}(f), the depth of f with respect to Ω, is the minimum depth of an Ω-circuit computing f.

Claim 1.4 Let Ω and Ω′ be complete finite bases, then for every f,

1. C_{Ω}(f) = Θ(C_{Ω′}(f))

2. D_{Ω}(f) = Θ(D_{Ω′}(f))

Proof: The proof is easy. By substituting each gate in a circuit over Ω with an equivalent circuit over Ω′, we obtain that C_{Ω′(f)} = O(C_{Ω}(f)) and that D_{Ω′(f)} = O(D_{Ω}(f)). The opposite direction is identical.

Theorem 1.5 ( Trivial lower bounds over B_{2}) If f : {0, 1}^{n} → {0, 1} depends essentially on all its variables, that is, for every 1 ≤ i ≤ n, the sub-functions of f for x_{i} = 0 and x_{i} = 1 are different, then

1. C_{B_{2}}(f) ≥ n − 1

2. D_{B_{2}}(f) ≥ ⌈log n⌉

Proof: The proof uses connectivity: the underlying graph of a minimal circuit B has at least n + c − 1 edges , where c = C_{B_{2}}(f). This is true because every variable must have an edge leaving it, and every gate, except the output gate, must also have an edge leaving it (otherwise it can be eliminated and the circuit B would not have been minimal). Each gate has two edges entering it, implying that the number of edges equals 2c. Hence 2c ≥ n + c − 1 and c ≥ n − 1, thus C_{B_{2}}(f) ≥ n − 1. Next, observe that a binary tree of depth k has at most 2^{k} leaves. The proof for D_{B_{2}}(f) follows easily.

1.4.2 Shannon’s Theorem

Surely, every function of n variables can be computed by a circuit of size O(n2^{n}). Further on, this upper bound will be improved to (1 + o(1))\frac{2^{n}}{n} . We now show that for almost every function, this upper bound is a tight bound.

Theorem 1.6 (Shannon,’49) For almost every function f ∈ B_{n}, we have C_{B_{2}}(f) ≥ \frac{2^{n}}{n}

Proof: The proof uses a counting argument: we estimate the number of Boolean circuits over B_{2} of size s with n input bits. We denote this number by C(n, s). For upper-bounding C(n, s), we bound the size of A, the family of Boolean circuits over B_{2} of size s with n input bits, and of which underlying graphs need not be acyclic. Each circuit in A has s gates with in-degree 2. Each such gate is labeled by a function from B_{2}, and for both its entering edges, each one of the (n + s) nodes can be chosen. Also, one of these gates is chosen to be the ‘output’ gate.

C(n, s) ≤ |A|, and hence

C(n, s) ≤ \frac{\overbrace{s}^{choose output} · [\overbrace{16}^{|B_{2}|} · \overbrace{(n + s)^{2}}^{# possible inputs}] \overbrace{s}^{# gates}}{\underbrace{s!}_{order does not count}}

The complexity measures C_{Ω}, D_{Ω} 7

By Stirling formula, s! ≥ (\frac{s}{e})^{s}, so by taking the logarithm out we have

log C(n, s) ≤ s·log 16(n+s)^{2} +log s−log s! ≤ 2s·log(n+s)+4s+log s−s·log s+s·log e ≤

(Assuming s ≥ n, we get ) ≤ 2s log 2s + 4s + log s − s · log s + s · log e = (s + 1) · log s + (6 + log e) · s . Now, take s = \frac{2^{n}}{n} and then

log C(n, s) ≤ (\frac{2n}{n} + 1) · (n − log n) + (6 + log e) · \frac{2^{n}}{n} = 2^{n} − \frac{2^{n}·log n}{n}(1 + o(1)).

Now returning to C(n, s), we conclude that the number of functions computable by circuits with at most \frac{2^{n}}{n} gates is 2^{2^{n}} · 2^{− \frac{2^{n}·log n}{n} (1+o(1))}, which is a very small proportion of the 2^{2^{n}} Boolean functions of n variables.

Bibliography

[1] R.B. Boppana & M. Sipser, “The Complexity of Finite Functions”, in “Handbook of Theoretical Computer Science” ed. J. van Leeuwen, Elsevier Science Publishers B.V., 1990, Vol A , Chapter 14, pp. 758-804.

[2] P. Dunne, “The Complexity of Boolean Networks”, Academic Press, 1989.

[3] I. Wegener, “The Complexity of Boolean Functions”, John Wiley & sons, 1987.