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.

  • $\begingroup$ Question is unanswerable without saying what set of gates you allow. $\endgroup$
    – orlp
    Aug 14 '19 at 21:52

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}$.

  • $\begingroup$ Of the 16 logical functions, 2 are constants, 2 just copy one input so they could be removed, and two negate one input so we could take just one of them with one input. Several are symmetrical so we can divide the number of inputs by 2. I wonder if that would substantially reduce the number of possible different circuits. $\endgroup$
    – gnasher729
    Jun 2 '20 at 8:17
  • $\begingroup$ There are also plenty of pairs if functions where f(a,b)=g(b,a) making one of them unnecessary. $\endgroup$
    – gnasher729
    Jun 2 '20 at 8:31
  • $\begingroup$ Yes, you can probably come up with tighter bounds of the number of different functions that can be computed by a circuit of size m. This just provides a loose bound for the number of circuits possible, and even under the (false and generous) assumption that each of those circuits generates a different function, shows that not all functions on n inputs can be constructed using fewer than 2^n/n gates. $\endgroup$ Jun 2 '20 at 20:47

Your Answer

