<p>Are there positive integers <span class="math-container">$k,c$</span> with the following property?</p>
<blockquote>
<p>Whenever <span class="math-container">$n$</span> is a positive integer, then any function <span class="math-container">$$f:\{0,1\}^n\to\{0,1\}$$</span> can be built using at most <span class="math-container">$n^k+c$</span> <span class="math-container">${\tt NAND}$</span>-gates with 2 inputs and 1 output.</p>
</blockquote>

CC BY-SA 4.0
2023-12-30T19:26:25.320Z
This is not a research-level question, and should have been asked at https://cs.stackexchange.com . Any textbook on circuit complexity will tell you that the maximal circuit size required by boolean functions in $n$ variables is $(1+o(1))2^n/n$ (and this is pretty much independent of the choice of the basic gate types). An $\Omega(2^n/n)$ lower bound actually follows by a trivial counting argument, as there are $2^{2^n}$ distinct functions, but only $2^{O(s\log(s+n))}$ circuits of size $s$.
Emil Jeřábek
CC BY-SA 4.0
2023-12-31T09:23:06.287Z
Thanks Emil for your helpful information and the counting argument that escaped me. Will delete the question. Happy new year!
Dominic van der Zypen
<boolean-functions>
Number of ${\tt NAND}$-gates needed to build any $n$-ary Boolean function
Dominic van der Zypen
# Number of ${\tt NAND}$-gates needed to build any $n$-ary Boolean function

(Asked by: username_0 on 2023-12-30)

Are there positive integers $k,c$ with the following property?

> Whenever $n$ is a positive integer, then any function $$f:\{0,1\}^n\to\{0,1\}$$ can be built using at most $n^k+c$ ${\tt NAND}$-gates with 2 inputs and 1 output.

**Tags:** boolean-functions
> **Comments:**
> **username_1**: This is not a research-level question, and should have been asked at https://cs.stackexchange.com . Any textbook on circuit complexity will tell you that the maximal circuit size required by boolean functions in $n$ variables is $(1+o(1))2^n/n$ (and this is pretty much independent of the choice of the basic gate types). An $\Omega(2^n/n)$ lower bound actually follows by a trivial counting argument, as there are $2^{2^n}$ distinct functions, but only $2^{O(s\log(s+n))}$ circuits of size $s$.  
> **username_0**: Thanks Emil for your helpful information and the counting argument that escaped me. Will delete the question. Happy new year!  

---

## 0 answers

