1
$\begingroup$

I'm trying to determine an asymptotic bound on the cardinality of the following set of functions. It is the functions with $n$-bit inputs, $\{0,1\}$ output, and requires precisely $n^2$ NAND gates. I'm trying to show that this is $2^{o(n^3)}$.

I've thought about just counting all functions but that's too big, $2^{2^n}$. I've thought about all ways to wire up $n^2$ gates and the best bound that I can think of is to reason that each NAND has two wires in and one out. So each gate entails $\binom{n^2+n}{3}$ choices of wires in and out, by a rough over-count. Then you make a choice for each gate so that's $\binom{n^2+n}{3}^{n^2+n}$ by another rough over-count. But I believe this grows faster than $n!$ which is worse than $2^n$.

But any time I try to determine a more precise count of this set I just can't see the things I should count. When I think about writing a recurrence relation, that seems hopeless to write, let alone solve.

$\endgroup$

1 Answer 1

1
$\begingroup$

Note that $$ \binom{n^2+n}{3}^{n^2+n} = O(n^2)^{O(n^2)} = 2^{O(n^2\log n)} = 2^{o(n^3)}. $$ In fact, using this kind of calculation you can show that most $n$-bit functions require circuits of length $\Omega(2^n/n)$.

$\endgroup$

Your Answer

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

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