Skip to main content
Added a few more "interesting" details, beyond the plain answer to the exact question.
Source Link
Luke Mathieson
  • 18.3k
  • 4
  • 59
  • 87

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.

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.

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.

Source Link
Luke Mathieson
  • 18.3k
  • 4
  • 59
  • 87

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.