2
$\begingroup$

Please forgive me if this question is trivial, I couldn’t come up with an answer (nor finding one).

In order to show that there are boolean functions $f : \{0,1\}^n \rightarrow \{0,1\}$ which can be computed only using circuits of size $\Omega(2^n/n)$, we use a counting argument: there are at most $O(2^{k \log k})$ circuits of size $k$, and $2^{2^n}$ such functions.

Suppose that I am interested in counting circuits of size $k$ that compute different functions. The "simple" counting argument won't work since it may be possible that two "syntactically" different circuits actually compute the same function. In other words, I want to bound the size of the set: $$F = \{ f: \{0,1\}^n \rightarrow \{0,1\} | f \text{ can be computed using a circuit of size }k \} $$

Then $|F| < $ the number of circuits of size $k$ (since any circuit computes one function), but how can I bound $|F|$ from below? (i.e. $ x <|F|$)

$\endgroup$
1
$\begingroup$

In order to bound the number of functions computed by circuits of size $k$, you have at least two options:

  • Construct a large number of circuits of size $k$, which by construction compute different functions.
  • Consider a natural probability distribution on circuits of size $k$, and estimate the probability that two random circuits compute the same function.

As an example, it is known that every function on $m$ variables can be computed by a circuit of size $O(2^m/m)$. By considering functions of the form $f_1(x_1,\ldots,x_m) \lor \cdots \lor f_{n/m}(x_{n-m+1},\ldots,x_n)$, this shows that there are at least $(2^{2^m})^{n/m}$ different functions computed by circuits of size $k = O(n2^m/m^2)$. In terms of $k$, the number of functions is roughly exponential in $k\log k$, for $m \gg \log n$.

$\endgroup$
  • $\begingroup$ Thank you so much. Does the bound from your example is tight? Is there a known distribution or a set of circuits that is shown to be tight? $\endgroup$ – Judy L. Jul 22 '20 at 13:04
  • $\begingroup$ The bound is tight up to the constant in the exponent. I imagine that better bounds are known. $\endgroup$ – Yuval Filmus Jul 22 '20 at 13:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.