2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.