TransWikia.com

Counting circuits with constraints

Computer Science Asked by Judy L. on November 23, 2021

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|$)

One Answer

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 $klog k$, for $m gg log n$.

Answered by Yuval Filmus on November 23, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP