Reviewing Bounds on the Circuit Size of the Hardest Functions

Gudmund Skovbjerg Frandsen
Peter Bro Miltersen

March 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})) \leq L(n) \leq\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 $\{\neg,\wedge,\vee\}$

Available as PostScript, PDF, DVI.

Last modified: 2005-03-21 by webmaster.