3
$\begingroup$

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.
$\endgroup$
5
  • 1
    $\begingroup$ Do you know how to show that some function on $n$ bits requires circuits of size $\Omega(2^n/n)$? It is (almost) exactly the same calculation. $\endgroup$ Oct 25 '20 at 12:04
  • $\begingroup$ I do not, but I'd love to read about that. In particular, how many different boolean circuits exist of a certain size? How does this number change when we also require that the circuits are monotone? $\endgroup$
    – Ido
    Oct 25 '20 at 12:30
  • $\begingroup$ It is extremely strange that someone would ask you to prove an extension of this classical result without explaining first the proof of that classical result. $\endgroup$ Oct 25 '20 at 12:31
  • $\begingroup$ You can find the proof in many places, for example these lecture notes. Jukna's monograph Boolean function complexity also contains a proof of a refined version of this result, showing that hardest function requires circuits of size $\sim 2^n/n$. $\endgroup$ Oct 25 '20 at 12:33
  • $\begingroup$ Thanks, I will read the proof. $\endgroup$
    – Ido
    Oct 25 '20 at 14:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.