1
$\begingroup$

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

Thanks!

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

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.

$\endgroup$

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