Reviewing Bounds on the Circuit Size of the Hardest Functions

Forfattere

  • Gudmund Skovbjerg Frandsen
  • Peter Bro Miltersen

DOI:

https://doi.org/10.7146/brics.v12i9.21875

Resumé

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

Downloads

Publiceret

2005-03-11

Citation/Eksport

Frandsen, G. S., & Miltersen, P. B. (2005). Reviewing Bounds on the Circuit Size of the Hardest Functions. BRICS Report Series, 12(9). https://doi.org/10.7146/brics.v12i9.21875