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 {\displaystyle k} solvable by circuits of weft bounded by a positive integer w {\displaystyle w} and arbitrary positive integral depth d {\displaystyle d} , where d {\displaystyle d} has to be uniform in the problem parameters, in particular k {\displaystyle k} .
References