BRICS

Basic Research in Computer Science

Reviewing Bounds on the Circuit Size of the Hardest Functions

Gudmund Skovbjerg Frandsen Peter Bro Miltersen BRICS Report Series RS-05-9 ISSN 0909-0878 March 2005 BRICS RS-05-9 Frandsen & Miltersen: Reviewing Bounds on the Circuit Size of the Hardest Functions Copyright \begin{matrix}c \\ ◯ \end{matrix} 2005, Gudmund Skovbjerg Frandsen & Peter Bro

Miltersen. BRICS, Department of Computer Science University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent BRICS Report Series publications. Copies may be obtained by contacting:

BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK–8000 Aarhus C Denmark

Telephone: +45 8942 3360
Telefax: +45 8942 3255
Internet: BRICS@brics.dk

BRICS publications are in general accessible through the World Wide Web and anonymous FTP through these URLs:

http://www.brics.dk
ftp://ftp.brics.dk

This document in subdirectory RS/05/9/

Reviewing Bounds on the Circuit Size of the Hardest Functions

Gudmund Skovbjerg Frandsen Peter Bro Miltersen BRICS^{∗}

Department of Computer Science, University of Aarhus, IT-parken, Aabogade 34, DK-8200 Aarhus N, Denmark

   Email: {gudmund,bromille}@daimi.au.dk

March 16, 2005

Abstract

In this paper we review the known bounds for L(n), the circuit size complexity of the hardest Boolean function on n input bits. The best known bounds appear to be

\frac{2^{n}}{n} (1 + \frac{log n}{n} − O(\frac{1}{n})) ≤ L(n) ≤ \frac{2^{n}}{n} (1 + 3\frac{log n}{n} + O(\frac{1}{n}))

However, the bounds do not seem to be explicitly stated in the literature. We give a simple direct elementary proof of the lower bound valid for the full binary basis, and we give an explicit proof of the upper bound valid for the basis {¬, ∧, ∨}. Keywords: Computational complexity

1 Introduction

Shannon introduced the Boolean circuit size as a complexity measure [1], and showed upper and lower bounds for the minimum number of gates, L(n), needed in a Boolean circuit for computing a hardest function in B_{n}, the set of Boolean functions with n inputs and 1 output. Shannon proved that for every ϵ > 0 and n sufficiently large [1]

∗ Basic Research in Computer Science (www.brics.dk), funded by the Danish National Research Foundation.

(1 − ϵ)\frac{2^{n}}{n} < L(n) < \frac{2^{n+2}}{n}

The first improvement came when Lupanov showed a better upper bound [2]:

L(n) ≤ \frac{2^{n}}{n} (1 + O(\frac{1}{\sqrt{n}}))

Lupanov essentially closed the gap so that together with Shannons original lower bound it was now known that

L(n) = \frac{2^{n}}{n} ± o(\frac{2^{n}}{n})

Later Lutz showed that for every real α < 1 and almost every n [3]

\frac{2^{n}}{n} (1 + α\frac{log n}{n}) < L(n)

Lutz really showed a much more general result, and we give in section 2 a simple direct proof that

\frac{2^{n}}{n} (1 + \frac{log n}{n} − O(\frac{1}{n})) < L(n)

Our proof is robust in that a change of the basis or simple improvements seem only to effect the O(\frac{1}{n}) term. One might take this as an indication that it is also possible to give tight bounds on the second order term in the expression for L(n). It appears that several text book authors have observed that one can make a tighter analysis of Lupanovs construction [4, 5, 6], and they more or less explicitly deduce that L(n) ≤ \frac{2^{n}}{n} (1 + O(\frac{log n}{n})). We present such a tight analysis in section 3 where we particularly seek to minimize the constant hidden under the big-Oh notation obtaining the bound

L(n) ≤ \frac{2^{n}}{n} (1 + 3\frac{log n}{n} + O(\frac{1}{n}))

2 Lower bound

We will demonstrate the lower bound by showing how to transform a Boolean circuit into a list of instructions for a simple stack machine and then use a counting argument to bound the length of the latter.

Each instruction for the stack machine is either a push or a binary Boolean operation. Only the push operation has an argument, which is the number of an input or an (earlier) Boolean operation. Inputs are numbered 1, …, n, and Boolean operations are numbered n+1, …, n+s in a stack program with s Boolean operations. Execution of a push operation places an input or an earlier computed bit designated by the argument on top of the stack. Each Boolean operation removes the 2 topmost elements of the stack and writes a single element onto the stack. After execution of all instructions, there should be exactly one element left on the stack, namely the result.

Algorithm 1 Translation of circuit to stack program Require: circuit C of size s described as set of gates {g_{i} ← g_{i_{1}} op g_{i_{2}} | i =

n + 1, …, n + s} where g_{1}, …, g_{n} are inputs and g_{n+s} is output gate Ensure: Stack program P computes same function as C

1: Let P initially be empty 2: virtualPush(n + s)

Procedure virtualPush(i) 3: if g_{i} is an input then 4: add program line “push i” to P 5: if g_{i} is already computed by the jth Boolean operation in P then 6: add program line “push n + j” to P 7: if gate g_{i} ← g_{i_{1}} op g_{i_{2}} is not computed so far then 8: virtualPush(i_{1}) 9: virtualPush(i_{2}) 10: add program line “operation op” to P

Algorithm 1 describes a recursive procedure virtualPush that given the output gate of the circuit will construct a stack program computing the same function as the circuit, and the number of gates in the circuit will be equal to the number of Boolean operations in the stack program.

If the stack program contains s Boolean operations, then it contains s + 1 push operations. To see this observe that when executing the stack program, each push operation increases the stack size by one and each Boolean operation decreases the stack size by one. Since the stack is initially empty and it contains only the single output value at the end, there must be exactly s + 1 push operations.

The argument of a push operation can be represented by ⌈log(n + s)⌉ bits. A single bit is needed to distinguish push operations from Boolean operations, and 4 bits suffice to distinguish the Boolean operations. In total the stack program can be described using at most (s+1)(c+log(n+ s)) bits, for c = 7. Since there are 2^{2^{n}} distinct Boolean functions on n inputs, for some function the optimal circuit size s must satisfy that (s + 1)(c + log(n + s)) ≥ 2^{n}.

The last inequality implies that s > 2^{n}/n · (1 + log n/n − c/n) for n sufficiently large. We will argue this lower bound by way of contradiction, so we assume that s ≤ 2^{n}/n · (1 + log n/n − c/n), which by a simple rewriting is equivalent to n + s ≤ 2^{n}/n · (1 + log n/n − c/n + n^{2}/2^{n}). Using that log(1 + x) ≤ x log e, the assumption implies that log(n + s) ≤ n − log n + (log n/n − c/n + n^{2}/2^{n}) log e. Combining with the inequality of the previous paragraph, we see that

2^{n} ≤ (s + 1)(c + log(n + s))
≤ \frac{2^{n}}{n} (1 + \frac{log n}{n} − \frac{c}{n} + \frac{n}{2^{n}})(n − log n + c + (\frac{log n}{n} − \frac{c}{n} + \frac{n^{2}}{2^{n}}) log e)
≤ \frac{2^{n}}{n^{2}} (n + log n − c + \frac{n^{2}}{2^{n}})(n − log n + c + (\frac{log n}{n} − \frac{c}{n} + \frac{n^{2}}{2^{n}}) log e)
≤ \frac{2^{n}}{n^{2}} (n^{2} − log^{2} n + O(log n))
< 2^{n} for n sufficiently large

Thus we have a contradiction proving that s > 2^{n}/n · (1 + log n/n − c/n) for n sufficiently large.

Note that the two most significant terms in the bound seem robust. Simple restrictions on the basis or any simple improvements in the stack representation seem only to influence the value of c. One might also try to improve the lower bound by using that many stack programs compute the same Boolean function. By changing the order of lines 8 and 9 in Algorithm 1 (and changing the Boolean operation in line 10 correspondingly), one may generate up to 2^{s} distinct stack programs that all compute the same Boolean function. However, a formalisation of this argument will only influence the value of c, and cannot change the two most significant terms in the bound.

We have shown Theorem 1

L(n) ≥ \frac{2^{n}}{n} (1 + \frac{log n}{n} − O(\frac{1}{n}))

3 Tight analysis of Lupanovs upper bound

Recall the (k, s)-Lupanov representation of a Boolean function f on n bits as it is described by Savage [6].

This representation has the form

f(x) = ⋁_{i=1}^{p} ⋁_{v} f_{i,v}^{(r)}(a) ∧ f_{i,v}^{(c)}(b)

where input x = (x_{1}, …, x_{n}) is divided in two parts a = (x_{1}, …, x_{k}) and b = (x_{k+1}, …, x_{n}). The 2^{k} possible a-tuples of bits are divided into p = ⌈2^{k}/s⌉ lists A_{1}, …, A_{p} containing s tuples each (though A_{p} may contain fewer tuples). v ranges over bit tuples of length s. f_{i,v}^{(c)}(b) = 1 precisely when v describes the table of function values f(a, b) arising when a runs through the tuples in A_{i}. f_{i,v}^{(r)}(a) = 1 precisely when there is some j such that a is the jth tuple in A_{i} and the jth bit of v is 1.

A circuit for f may be constructed in three steps. In the first step, we use 2(2^{k} + 2^{n−k}) gates to compute all minterms over a and b. In the second step we use p2^{n−k} or-gates to compute f_{i,v}^{(c)} for all i, v, and we use p2^{s} or-gates to compute f_{i,v}^{(r)} for all i, v. In the third step f is computed using 2p2^{s} gates.

Arguments for these bounds are given by both Wegener [5] and Savage [6] except for our bound p2^{s} on the computation of f_{i,v}^{(r)}, where they mention only the weaker bound 2^{k+s}. To see that our bound is valid, observe that we may compute f_{i,v}^{(r)} separately for each i. This accounts for the factor p. For a fixed i we first compute those f_{i,v}^{(r)} where v contains a single 1-bit, then those where v contains two 1-bits, etc. In this way we need only use one or-gate per v, implying the stated bound.

By the above arguments we need at most 2(2^{k} + 2^{n−k}) + p2^{n−k} + 3p2^{s} gates to compute f. We may eliminate p from the expression, when using that p ≤ 1 + 2^{k}/s. This results in the upper bound 2^{n}/s + 2 · 2^{k} + 3(2^{n−k} + 2^{s} + 2^{k+s}/s) on the number of gates. Taking k = ⌈2 log n⌉ and s = ⌈n − 3 log n⌉, all terms but the first are bounded by O(2^{n}/n^{2}) and we may bound the first term separately

\frac{2^{n}}{s} ≤ \frac{2^{n}}{n − 3 log n}

= \frac{2^{n}}{n} (1 + \frac{3 log n}{n − 3 log n})
= \frac{2^{n}}{n} (1 + 3\frac{log n}{n} + O(\frac{log^{2} n}{n^{2}}))

Combining the bounds, we have shown Theorem 2

L(n) ≤ \frac{2^{n}}{n} (1 + 3\frac{log n}{n} + O(\frac{1}{n}))

Acknowledgment We would like to thank the anonymous referee for comments that greatly improved the presentation of the results.

References

[1] C. E. Shannon, The synthesis of two-terminal switching circuits, Bell System Tech. J. 28 (1949) 59–98.

[2] O. B. Lupanov, The synthesis of contact circuits, Dokl. Akad. Nauk SSSR (N.S.) 119 (1958) 23–26.

[3] J. H. Lutz, Almost everywhere high nonuniform complexity, J. Comput. System Sci. 44 (2) (1992) 220–258.

[4] R. G. Nigmatullin, Slozhnost bulevykh funktsii, Kazan. Gos. Univ., Kazan′, 1983.

[5] I. Wegener, The complexity of Boolean functions, Wiley-Teubner Series in Computer Science, John Wiley & Sons Ltd., Chichester, 1987.

[6] J. E. Savage, Models of Computation, Addison Wesley, 1998.

Recent BRICS Report Series Publications

RS-05-9 Gudmund Skovbjerg Frandsen and Peter Bro Miltersen. Reviewing Bounds on the Circuit Size of the Hardest Functions. March 2005. 6 pp. To appear in Information Processing Letters.

RS-05-8 Peter D. Mosses. Exploiting Labels in Structural Operational Semantics. February 2005. 15 pp. Appears in Fundamenta Informaticae, 60:17–31, 2004.

RS-05-7 Peter D. Mosses. Modular Structural Operational Semantics. February 2005. 46 pp. Appears in Journal of Logic and Algebraic Programming, 60–61:195–228, 2004.

RS-05-6 Karl Krukow and Andrew Twigg. Distributed Approximation of Fixed-Points in Trust Structures. February 2005. 41 pp.

RS-05-5 A Dynamic Continuation-Passing Style for Dynamic Delimited Continuations. Dariusz Biernacki and Olivier Danvy and Kevin Millikin. February 2005.

RS-05-4 Andrzej Filinski and Henning Korsholm Rohde. Denotational Aspects of Untyped Normalization by Evaluation. February 2005.

RS-05-3 Olivier Danvy and Mayer Goldberg. There and Back Again. January 2005. iii+16 pp. Extended version of an article to appear in Fundamenta Informatica. This version supersedes BRICS RS-02-12.

RS-05-2 Dariusz Biernacki and Olivier Danvy. On the Dynamic Extent of Delimited Continuations. January 2005. ii+30 pp.

RS-05-1 Mayer Goldberg. On the Recursive Enumerability of Fixed-Point Combinators. January 2005. 7 pp. Superseedes BRICS report RS-04-25.

RS-04-41 Olivier Danvy. Sur un Exemple de Patrick Greussay. December 2004. 14 pp.

RS-04-40 Mads Sig Ager, Olivier Danvy, and Henning Korsholm Rohde. Fast Partial Evaluation of Pattern Matching in Strings. December 2004. 22 pp. To appear in TOPLAS. Supersedes BRICS report RS-03-20.