3
$\begingroup$

The following result, by Lupanov, is a classic in the theory of Boolean function complexity:

Theorem: For every boolean function $f$ of $n$ variables: $$C(f) \leq (1 + \alpha_n)\frac{2^n}{n}, \text{ with } \alpha_n = O(\frac{n}{\log n})$$ where $C(f)$ denotes the minimum size of a fanin-two circuit computing $f.$

The original proof, which is reproduced e.g. in Jukna's book, uses a rather intricate circuit construction. I have several questions about this result:

  1. Is there an easier way to see the looser upper bound of $O(2^n/n)$?
  2. I'm having trouble seeing intuitively why we would expect such a bound, and such a construction, a priori. Why would you believe we can do better than a bound of $O(2^n)$ from the DNF?
$\endgroup$
1
  • $\begingroup$ $\alpha_n$ is $o(1)$ rather than an unbounded function such as $O(n/\log n)$. Perhaps you meant $O((\log n)/n)$? (I'm out of office atm and can't check the sources.) $\endgroup$ Commented Nov 15, 2023 at 6:53

1 Answer 1

4
$\begingroup$
  1. Yes, there is a simpler construction, essentially due to Shannon.
  • For every $k$, all $2^{2^k}$ functions on $k$ variables can be implemented by a circuit of size $2^{2^k}$ (just take some implementation and then merge gates computing the same function).
  • For every $k$, all $2^k$ elementary conjunctions can be implemented by a circuit of size $O(2^k)$ (implement recursively, halving the set of variables on each step)
  • Every function $f(x_1, \dots, x_n)$ can be decomposed as $$f(x_1, \dots, x_n) = \bigvee_{a} f(x_1, \dots, x_k, a_{k+1}, \dots, a_n) x_{k + 1}^{a_{k + 1}} \dots x_n^{a_n}$$ where $x_i^1 = x_i$ and $x_i^0 = \neg{x_i}$.
  • Thus, to implement any function, it is enough to implement all functions of $k$ variables (which will include all $f(x_1, \dots, x_k, a_{k+1}, \dots, a_n)$), all conjunction of $n-k$ variables $x_{k + 1}, \dots, x_n$, and $2^{n-k}$ disjunctions. In total, we have complexity $$2^{2^k} + O(2^{n - k}),$$ by taking $k = \log(n - \log n)$, we get $O(2^n/n)$
  1. The construction matches the lower bound $\frac{2^n}{n}$, also due to Shannon (Theorem 1.14 in Jukna's book).
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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