Number of circuits with at most $m$ logic gates

Question

I'm working on the same exercise as described in this post:

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

In the answer there I don't understand how the number of circuits with at most $m$ gates was found to be $O(m^{4m})$. My construction of the number of gates required:

Let any logic gate in the circuit take 2 inputs, which could be any of the $n$ inputs or any of the $m-1$ other logic gates. Then there are ${{m+n-1}\choose{2}}$ possibilities for the inputs into any logic gate. There are 16 different functions that act on 2 inputs, so let there be $16{{m+n-1}\choose{2}}$ possibilities for the inputs and type for any logic gate. Lastly, since there are $m$ gates, there will be $16^m {{m+n-1}\choose{2}}^m$ possibilities for the entire circuit.

Now we can say ${{m+n-1}\choose{2}}^m < \frac{1}{2^m}(m+n-1)^{2m} < \frac{1}{2^m}(2m)^{2m}$ when $m = 2^n/\log n$ (or $2^n/n$), so $16^m {{m+n-1}\choose{2}}^m < (32m^2)^m$. So we would want to show that $(32m^2)^m$ is less than $2^{2^n}$. This doesn't seem to be true anywhere, so I must have made a mistake somewhere.

I've looked online a bit and have found three different sources say that the number of circuits with at most $m$ inputs is $m^2$, $2^m$, and something similar to what I came up with. I understand that which gates to use is vague, but these are fundamentally different functions, and I'm very confused.

Answer 1

I would recommend reading the Circuit Complexity lecture notes by Jonathan Katz, in which he discusses the problem clearly.

You start off on the right foot. For two-input, single-output gates, there are 16 different possible logical functions. Each of the two gate inputs can either be from another of the $m$ gates or from one of the $n$ inputs, which leaves $16(m+n)^2$ possibilities for the type of each gate. Since there are $m$ gates, at first glance there should be $(16(m+n)^2)^m$ different circuits we could construct from these gates.

However, we should also specifically select for the output gate, so we multiply the number of circuits by $m$ to account for this choice: thus we have a bound of $m\cdot(16(m+n)^2)^m$ different possible circuits of size $m$.

The crucial step that you are missing is that the labels we assigned to each of our gates were arbitrary, and thus we can divide our bound by $m!$ to compensate for our overcounting.

We thus have a tighter bound of $$\frac{m \cdot (16 (m+n)^2)^m}{m!}$$ for the number of circuits of size $m$.

If we assume $m = (1-\epsilon)\frac{2^n}{n}$, for any $\epsilon>0$, one can (and Katz does) show that this is less than $2^{2^n}$.