Weft (circuit)

In complexity theory, especially circuit complexity theory, the weft of a Boolean circuit is a measure of its complexity.

A Boolean circuit is a directed acyclic graph with its nodes being Boolean gates (AND, OR, NOT). There are 2 types of gates:

• Small gates: Gates with bounded fan-in, where the bound is specified at the start. Usually, this means fan-in of 1 for NOT, and fan-in of 1 or 2 for AND and OR.
• Big gates: Gates with fan-in larger than the bound.

The weft of a circuit is then the maximal number of big gates that any path from inputs to outputs must contain.

Compare this with the depth of a circuit, which is the maximal number of gates that any path from inputs to outputs must contain. The weft is used in parametrized complexity to define the W hierarchy which is a hierarchy of problems weighted by a positive integer parameter ${\displaystyle k}$ solvable by circuits of weft bounded by a positive integer ${\displaystyle w}$ and arbitrary positive integral depth ${\displaystyle d}$, where ${\displaystyle d}$ has to be uniform in the problem parameters, in particular ${\displaystyle k}$.^[1][2]

References

1. Downey, Rod G.; Fellows, Michael R. "Fixed-Parameter Tractability and Completeness I: Basic Results". SIAM Journal on Computing. 24 (4): 873–921. doi:10.1137/S0097539792228228. ISSN 0097-5397.
2. Downey, Rodney G.; Fellows, Michael R.; Regan, Kenneth W. (1998-01-30). "Parameterized circuit complexity and the W hierarchy". Theoretical Computer Science. 191 (1): 97–115. doi:10.1016/S0304-3975(96)00317-9. ISSN 0304-3975.