ECCC-Report TR05-032https://eccc.weizmann.ac.il/report/2005/032Comments and Revisions published for TR05-032en-usThu, 17 Mar 2005 08:55:19 +0200
Paper TR05-032
| Reviewing Bounds on the Circuit Size of the Hardest Functions |
Gudmund Skovbjerg Frandsen,
Peter Bro Miltersen
https://eccc.weizmann.ac.il/report/2005/032In 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\}$.
Thu, 17 Mar 2005 08:55:19 +0200https://eccc.weizmann.ac.il/report/2005/032