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.
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Well, either en.wikipedia.org/wiki/Constructive_proof or en.wikipedia.org/wiki/… $\endgroup$– adrianNOct 10, 2017 at 8:45
-
1$\begingroup$ Your title is way more general than your actual question. Please formulate a better one. $\endgroup$– Raphael ♦Oct 10, 2017 at 11:15
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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.)
answered Oct 10, 2017 at 8:54
-
1$\begingroup$ As I'm sure you have already guessed, the question came from an exercise in a textbook, so that must be a typo/error. Thank you for clarifying this. $\endgroup$ Oct 10, 2017 at 9:01
-
1$\begingroup$ Shouldn't it be $f(m)=O(m)^{2m^4}$? (Instead of $f(m)=O(m)^{4m}$) Reason: We have at most $m^2$ binary gates, each can be described $O(m^4)$ different ways so: $\left(m^2\right)^{m^4}=m^{2m^4}$ $\endgroup$ Sep 28, 2020 at 17:43
-
1$\begingroup$ Possibly, though it makes little difference here (unless you care about constants). $\endgroup$ Sep 28, 2020 at 18:19