Most Boolean function on N input requires exponential (as a function of N) number of 2-input Boolean gates.

Problem:

Most Boolean function on N input requires exponential (as a function of N) number of 2-input Boolean gates.

Proof idea:

The number of Boolean function is huge (i.e. exponential exponential) but the number of circuit you can make out of polynomial number of gates is smaller than that.

Proof:

The number of Boolean functions of n input can be counted by listing the output of the Boolean function output starting from

00000..000 = 0
00000..001 = 0
...

There are $2^n$ rows, therefore every unique bit string of length $2^n$ represents an unique Boolean function, so we have $2^{2^n}$ Boolean functions.

On the other hand, if we have a polynomial number of gates, they could be arranged in anyway, the number of circuits could be at most $(cn^s)! < 2^{cn^s} < 2^{2^n}$, therefore, most of the circuits do require more than polynomial number of gates.