Reviewing Bounds on the Circuit Size of the Hardest Functions

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