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

CC BY-SA 4.0
2023-11-14T20:11:54.247Z
2024-01-05T10:45:40.893Z
2024-01-05T10:45:40.893Z
Vladimir Lysikov
<p>The following result, by Lupanov, is a classic in the theory of Boolean function complexity:</p>
<blockquote>
<p><strong>Theorem</strong>:  For every boolean function <span class="math-container">$f$</span> of <span class="math-container">$n$</span> variables:
<span class="math-container">$$C(f) \leq (1 + \alpha_n)\frac{2^n}{n}, \text{ with } \alpha_n = O(\frac{n}{\log n})$$</span>
where <span class="math-container">$C(f)$</span> denotes the minimum size of a fanin-two circuit computing <span class="math-container">$f.$</span></p>
</blockquote>
<p>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:</p>
<ol>
<li>Is there an easier way to see the looser upper bound of <span class="math-container">$O(2^n/n)$</span>?</li>
<li>I'm having trouble seeing intuitively why we would expect such a bound, and such a construction, <em>a priori.</em> Why would you believe we can do better than a bound of <span class="math-container">$O(2^n)$</span> from the DNF?</li>
</ol>

CC BY-SA 4.0
2023-11-15T06:53:36.557Z
$\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.)
Emil Jeřábek
<cc.complexity-theory><circuit-complexity><boolean-functions>
Intuition on Lupanov's Upper Bound on Circuit Size
sdsdsd
# Intuition on Lupanov's Upper Bound on Circuit Size

(Asked by: username_0 on 2023-11-14)

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?

**Tags:** cc.complexity-theory, circuit-complexity, boolean-functions
> **Comments:**
> **username_1**: $\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.)  

---

## 1 answers

### Answer by username_2 on 2023-11-14. Score: 4 | Accepted answer

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

2. The construction matches the lower bound $\frac{2^n}{n}$, also due to Shannon (Theorem 1.14 in Jukna's book).


---

