How many circuits are of size $n$ are there? In general for a size $n$ circuit, I know there are $O(2^{poly(n)})$ circuits$^1$, but surely this is reduced by the succinctness condition?

$^1$ https://cs.stackexchange.com/questions/89488/proving-that-exp-doesnt-have-polynomial-size-circuits

  • $\begingroup$ What exactly do you mean by “succinctly generated circuits”, and how do you measure their size? Note that in general, only $2^{O(n)}$ objects can be described (using whatever fixed encoding scheme) by strings of length $n$ in a finite alphabet. $\endgroup$ – Emil Jeřábek Feb 8 at 19:02
  • $\begingroup$ Size here meaning the number of gates in the circuit. I appreciate that in general there are only $2^{O(n)}$ circuits for an $n$ bit entry. But does that necessarily tell me anything about the size? Does it straightforwardly imply there are only $log(n)$ circuits with $n$ gates that can be described in any succinct encoding scheme? $\endgroup$ – user138901 Feb 8 at 20:45
  • $\begingroup$ No, a more likely bound is $n^{O(1)}$ if the encoding produces exponentially larger circuits, but this entirely depends on the encoding scheme, of which you still haven’t specified one iota. $\endgroup$ – Emil Jeřábek Feb 9 at 7:51

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.