Show there exists a monotone function $f\colon \{0,1\}^n \mapsto \{0,1\}$, such that the minimal size of a monotone circuit that computes $f$ is $\Omega(2^n / n^2)$. Use the fact that the number of monotone functions is at least $2^{\frac{2^n}{2 \sqrt{n}}}$.
Every monotone $f\colon \{0,1\}^n \to \{0,1\}$ has a minimal size monotone circuit $C_f$ that computes $f$. Since there are at least $2^{\frac{2^n}{2 \sqrt{n}}}$ functions such as $f$, there are at least $2^{\frac{2^n}{2 \sqrt{n}}}$ circuits such as $C_f$.
Assume the minimal size of a monotone circuit that implements a monotone function $f\colon \{0,1\}^n \to \{0,1\}$ is $o(2^n / n^2)$. Fix some $c\in \mathbb{R}^+$. There exists some $N$, such that for every $n>N$ it holds that $\mathrm{Size}(C_f) \leq c\cdot \frac{2^n}{n^2}$.
I am trying to show that the number of possible monotone circuits $C_f$ on $n>N$ inputs - whose size is minimal and bounded by $c\cdot \frac{2^n}{n^2}$ - is less than the number of monotone functions $f$. This would mean the assumption I made leads to a contradiction, and thus the opposite is true.
Can you help me solve this problem?
- $f\colon \{0,1\}^n \to \{0,1\}$ is monotone if for every $x,y\in \{0,1\}^n$ such that $x_i \leq y_i $ for all $i$, it holds that $f(x) \leq f(y)$.
- A circuit $C(x_1,\ldots,x_n)$ is monotone if it only has AND gates and OR gates.
