Open AccessReviewing Bounds on the Circuit Size of the Hardest Functions
Author(s) -
Gudmund Skovbjerg Frandsen,
Peter Bro Miltersen
Publication year - 2005
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v12i9.21875
Subject(s) - boolean function , combinatorics , upper and lower bounds , mathematics , binary number , simple (philosophy) , basis (linear algebra) , function (biology) , discrete mathematics , circuit complexity , arithmetic , electronic circuit , physics , mathematical analysis , philosophy , geometry , epistemology , quantum mechanics , evolutionary biology , biology
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)) 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}.