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.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
answered Mar 1, 2013 at 1:03
$\begingroup$
$\endgroup$
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.
