# What does “number of gates” mean in circuit complexity?

By "number of gates", I am wondering whether these gates include AND/OR gates that can receive several inputs or they just include AND/OR gates that receive two inputs.

The number of inputs to a gate is an independent restriction or allowance on the circuit. The number of gates in a circuit is simply the number of gates.

Of course you can always measure the two separately. For example the $W$-hierarchy in Parameterized Complexity can be defined in terms of the large-gate depth (called in this context the weft) of families of circuits (i.e. the maximum number of gates with unbounded fan-in on any path from the inputs to the output).

Of course we can also take an unbounded fan-in gate (if we're sticking to AND/OR at least) and replace it with a circuit consisting of a several bounded fan-in gates, but the size may increase significantly.

In the general sense Luke is right, there is no relation between the number of gates and fa-in.

But in the literature what authors mean depends on the context. Note that by itself the number of gates is not a robust notion. What kind of circuits are we talking about?

If we are talking about unbounded fan-in circuits for $\mathsf{AC^0}$ then we count each gate as one no matter what the fan-in is.

If we are talking about bounded fan-in circuits for $\mathsf{NC^1}$ then you should convert each such gate first into a number of bounded fan-in gate and then count it.