# How to show that hard-to-compute Boolean functions exist?

How can one show that there exist Boolean functions on $n$ inputs which require at least $2^n/\log{n}$ logic gates to compute?

This problem was originally stated in Exercise 3.16 of Nielsen & Chuang's Quantum Computation and Quantum Information.

• – adrianN Oct 10 '17 at 8:45
• Your title is way more general than your actual question. Please formulate a better one. – Raphael Oct 10 '17 at 11:15

There are only so many circuits using at most $m$ gates, say $f(m)$. If all Boolean functions on $n$ inputs could be computed using at most $m$ gates, then $f(m) \geq 2^{2^n}$, since there are $2^{2^n}$ Boolean functions on $n$ inputs. Hence if $f(m) < 2^{2^n}$ then there must be a function on $n$ inputs which cannot be computed using at most $m$ gates.
A Boolean circuit with $m$ unbounded fan-in gates can be simulated using at most $m^2$ binary gates. We can describe each binary gate by satisfying its inputs and its type (AND, OR, NOT), for a total of $O(m^4)$ possibilities per gate. This leads to a rough bound $f(m) = O(m)^{4m}$. If $m = C 2^n/n$ then $$f(m) = \exp O(m\log m) = \exp O(C 2^n),$$ and so for an appropriate choice of $C$, we would get $f(m) < 2^{2^n}$. This shows that there are some Boolean functions which require at least $C 2^n/n$ gates to compute. It turns out that (up to the choice of $C$) this bound is tight. (So what you wrote in your post is actually wrong.)