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.

  • 3
    $\begingroup$ This is not a research-level question, and should have been asked at 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$. $\endgroup$ Dec 30, 2023 at 19:26
  • $\begingroup$ Thanks Emil for your helpful information and the counting argument that escaped me. Will delete the question. Happy new year! $\endgroup$ Dec 31, 2023 at 9:23


Your Answer

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

Browse other questions tagged or ask your own question.