Talk:Circuit complexity

history

I thought this started with Shannon's theorem that a random Boolean function on n variables takes O(2^n) gates. 66.127.54.226 (talk) 18:14, 21 September 2010 (UTC)

You mean $\Omega (2^{n}/n)$, I suppose.—Emil J. 15:16, 22 September 2010 (UTC)

Size of unbounded-fan-in circuits

The size of circuits with unbounded fan-in is defined as the number of wires, not number of gates. See e. g. Reischuk, Karl Rüdiger (1990). Einführung in die Komplexitätstheorie. Hrsg.von Hans-Jürgen Appelrath u.a. Teubner or https://arxiv.org/abs/2204.06618 (page 801). 1802sanj0 (talk) 09:29, 23 May 2025 (UTC)