Weft (circuit)

Template:Short description 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 $k$ solvable by circuits of weft bounded by a positive integer $w$ and arbitrary positive integral depth $d$, where $d$ has to be uniform in the problem parameters, in particular $k$.