For simplicity, we can assume that only NAND gates are allowed. An asymptotically correct solution is all I really need.



closed as unclear what you're asking by D.W., FrankW, David Richerby, Juho, vonbrand Apr 11 '14 at 19:31

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ What do you think? What have you tried? Where did you get stuck? $\endgroup$ – Yuval Filmus Apr 8 '14 at 2:45

Hint: Each of the $s$ gates is connected to two other gates or inputs, for a total of $(s+n)^2$ possibilities. This gives a rough upper bound which isn't tight, but is good enough for many purposes, for example to show that some functions require circuits of size $\Omega(2^n/n)$. See Steurer's notes, for example.


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