Prove that the number of circuits with bounded fan-in (of 2) of size $s$ is at most $s^{O(s)}$.
Give the best explicit bound you can get.

I know that for a circuit of size $s$ in order to generate a string to represent it I need for every edge, which I have at most $s$ of those, to represent from which vertex it start and in which vertex it ends and for that I need $2s \log s$ bits. In addition I need another 2 bit for every vertex to mark whether it is an input, an OR/AND/NOT Gate. So overall I need $O(s \log s)$ bits to represent a circuit, and there are $2^{O(s \log s)} = s^{O(s)}$ circuits like that.

Am I in the right direction or am I missing something? And is $2^{3(s \log s)} = 8s^{O(s)}$ the bound?

  • $\begingroup$ Your question already contains a complete solution. We're not here to grade your homework. We can help you if you have a particular doubt. $\endgroup$ Oct 26 '20 at 16:46
  • $\begingroup$ I wasn't sure if I was correct so that is why I posted this question. The only part I'm not sure about is how can I identify each input node, because saving also the indices of every one of them is another $slogs$, or maybe the information I stored so far is enough? $\endgroup$
    – Emma
    Oct 26 '20 at 17:05
  • $\begingroup$ The simplest solution is to have the first $n$ vertices contain the $n$ inputs. $\endgroup$ Oct 26 '20 at 17:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.