= Uniform circuit family
A <uniform circuit family> $(C_n)$ has one effective rule generating its circuits rather than an independently supplied design at every <input> length. The precise resource limit on this rule is part of the definition. In <uniform circuit family>[logspace uniformity], a <Turing machine> given $1^n$ <output>[outputs] a description of $C_n$ using $O(\log n)$ <space complexity>[work space]; its <output> tape is not counted as <space complexity>[work space].
A family of balanced <AND gate> trees is uniform: a procedure can enumerate <logic gate>[gates] and their connections from the <input> length. In contrast, a nonuniform family can choose the constant <output> at length $n$ using membership of $n$ in an undecidable set. Those constant circuits are individually tiny, but no <algorithm> can generate the whole family. Uniformity therefore distinguishes small circuits that can be constructed effectively from arbitrary advice hidden in their choice. Stronger local-access conventions are also used when the circuit depth is so small that the cost of generating a complete description would obscure the intended complexity bound.
Back to article page
