Weft (circuit)
From Wikipedia, the free encyclopedia
In complexity theory, especially circuit complexity theory, the weft of a Boolean circuit is a measure of its complexity.
A Boolean circuit is an acyclic directed 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.[1][2]
