TR05-032 Authors: Gudmund Skovbjerg Frandsen, Peter Bro Miltersen

Publication: 17th March 2005 08:55

Downloads: 2543

Keywords:

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\}$.