World's most popular travel blog for travel bloggers.

How many size $s$ circuits from $\{0, 1\}^n \to \{0, 1\}$ are there?

, , No Comments
Problem Detail: 

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


Asked By : GMB
Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback