Reviewing Bounds on the Circuit Size of the Hardest Functions - Frandsen, Gudmund Skovbjerg; Miltersen, Peter Bro (BRICS Report Series, 2005)
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 2^n / n (1 + log n / n - O(1/n)) <= L(n) <= 2^n / n (1 + 3 log n / n + O(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 {not, and, or}.