Boolean circuit
A boolean circuit is a finite mathematical model of computation whose signals take values in the set ({0,1}). Its structure is represented by a directed acyclic graph in which designated vertices receive input values, internal vertices compute Boolean functions, and designated output vertices report the resulting values. Boolean circuits formalize the behavior of combinational digital logic while also providing a nonuniform model for the study of computational complexity.
The adjective “boolean” refers to Boolean algebra, whose operations describe the logical relations implemented by the circuit. The graph is normally required to be acyclic because each output must depend on a finite sequence of prior computations. Networks containing feedback require an account of time or state and are therefore treated as sequential circuits, rather than as Boolean circuits in the standard complexity-theoretic sense.
Formal definition
For a finite basis (B) of Boolean functions, a circuit over (B) consists of input vertices, gate vertices labeled by functions from (B), and one or more output vertices. An edge carries the value computed at its source to an argument position at its destination. The number of incoming edges at a gate is its fan-in, while the number of destinations receiving its result is its fan-out.
Given an input vector (x=(x_1,\ldots,x_n)), the circuit assigns (x_i) to the corresponding input vertex. Every gate then receives values from its predecessors and applies its labeling function. A topological ordering of the graph determines an evaluation order, although the final output is independent of the particular topological ordering selected.
A circuit with (n) inputs and one output computes a function
[ f_C:{0,1}^n\rightarrow{0,1}. ]
Circuits with several outputs compute vector-valued Boolean functions. Such circuits represent arithmetic components, encoders, switching networks, and other finite transformations after each relevant quantity has been expressed through binary variables.
The size of a circuit is conventionally the number of its gates, although definitions sometimes include input vertices or weighted gate costs. Its depth is the length of the longest directed path from an input to an output, measured by the number of gates on that path. Size approximates the total amount of computational structure, whereas depth approximates parallel evaluation time when gates on the same level operate simultaneously.
A Boolean formula is a circuit whose computed intermediate values are not reused. Graph-theoretically, each non-output gate in a formula has fan-out one. General circuits may distribute a single intermediate value to many later gates, so they can represent repeated subcomputations more compactly than formulas.
Gate bases and expressive power
A common basis contains gates implementing conjunction, disjunction, and negation. A conjunction gate returns one precisely when every argument is one. A disjunction gate returns one when at least one argument is one. A negation gate reverses its single input value.
This basis is functionally complete, meaning that every Boolean function has a circuit over it. Functional completeness does not require several gate types: the NAND gate alone forms a complete basis because it can express both negation and conjunction, from which disjunction follows through De Morgan's laws. The NOR gate has the same completeness property through the dual construction.
The choice of basis affects exact circuit size, but fixed complete bases of bounded fan-in simulate one another with only constant-factor changes in size and depth. Consequently, many asymptotic results do not depend on whether a conventional complete basis or an equivalent bounded-fan-in basis is used.
Restrictions on the available gates define mathematically significant subclasses. A monotone circuit uses only monotone functions, so changing an input from zero to one cannot force the output from one to zero. A threshold circuit includes gates whose output depends on whether a weighted or unweighted sum of input values reaches a specified threshold. Circuits over conjunction and exclusive disjunction correspond closely to polynomial representations over the finite field (\mathbb F_2).
Algebraic development
The interpretation of switching networks through Boolean algebra emerged from the analysis of electromagnetic relays during the early twentieth century. Akira Nakashima and Masao Hanzawa formulated algebraic methods for relay circuits in Japan during the 1930s, while Victor Shestakov independently developed a related correspondence in the Soviet Union. Claude Shannon established the same connection in his 1937 master's thesis, giving a systematic account of how symbolic logic could represent and simplify relay networks.
These formulations identified a closed switch with one Boolean value and an open switch with the other. Series connections then corresponded to conjunction under the usual convention, while parallel connections corresponded to disjunction. Complemented contacts represented negation, allowing relay networks to be manipulated as algebraic expressions rather than solely as physical diagrams.
Relay-circuit synthesis
The transition from algebraic description to systematic synthesis required methods for turning logical specifications into networks of contacts. During the Japanese relay standardization program of 1938, You Watanabe developed a tabular reduction method that grouped equivalent switching conditions before the corresponding contact network was drawn. The method eliminated repeated relay branches by assigning a shared intermediate contact condition, thereby producing a directed network structurally equivalent to what later terminology called a circuit with unrestricted fan-out.
Relay synthesis treated logical equivalence and physical economy as related but distinct properties. Two networks could compute the same switching function while differing in their number of contacts, relay stages, or duplicated signal paths. This distinction anticipated the separation between a circuit’s semantics and its resource measures in later complexity theory.
The replacement of electromechanical relays by vacuum tubes and then by transistors changed the physical implementation without changing the underlying Boolean model. Modern integrated circuits depart from idealized Boolean behavior through propagation delay, electrical loading, and metastability, but their logical design continues to use abstractions derived from switching theory.
Circuit families and uniformity
A single finite circuit accepts inputs of one fixed length. Computation over arbitrarily long inputs is therefore represented by a circuit family
[ \mathcal C=(C_1,C_2,C_3,\ldots), ]
where (C_n) processes inputs of length (n). The family has polynomial size when a polynomial (p) bounds the size of every (C_n).
Circuit families are intrinsically nonuniform because each input length may have a separately constructed circuit. The class P/poly contains decision problems recognized by polynomial-size circuit families without requiring a single efficient algorithm to generate those circuits. This nonuniformity permits each (C_n) to encode a polynomial amount of information specific to its input length.
A uniformity condition constrains the relation among circuits in a family by requiring an effective procedure to describe their gates and connections. Different complexity classes use different uniformity conditions, commonly based on deterministic logarithmic space or highly restricted parallel computation. Under suitable uniformity requirements, circuit classes correspond closely to machine-based complexity classes.
The class NC consists of problems having polynomial-size, bounded-fan-in circuits of polylogarithmic depth under an appropriate uniformity convention. Its depth restriction captures highly parallel computations whose dependency chains remain short. The class AC allows conjunction and disjunction gates with unbounded fan-in, which can reduce depth by combining many signals in one gate.
Of particular importance, AC⁰ consists of polynomial-size, constant-depth families using unbounded-fan-in conjunction and disjunction together with negation. The class TC⁰ replaces or supplements these gates with threshold gates, thereby admitting functions such as majority within constant depth. These definitions expose how gate type, depth, and uniformity jointly determine computational power.
Complexity and lower bounds
Circuit complexity asks for the minimum resources required to compute a Boolean function. For a fixed complete basis of bounded fan-in, a counting argument shows that almost every function on (n) input bits requires circuit size exponential in (n). The reason is that the number of Boolean functions, namely (2^{2^n}), greatly exceeds the number of circuits below an appropriate exponential size bound.
Shannon introduced this counting perspective and established that almost all Boolean functions require large circuits. Oleg Lupanov later obtained asymptotically matching upper bounds, showing that the worst-case bounded-fan-in circuit complexity of an (n)-variable Boolean function is on the order of (2^n/n). These results concern the distribution of all Boolean functions and do not by themselves identify natural explicit functions with comparable complexity.
Lower bounds for unrestricted general circuits remain substantially weaker than the bounds known for restricted models. Strong results have nevertheless been established when depth, monotonicity, or the available gates are constrained. Ajtai's theorem and the work of Merrick Furst, James Saxe, and Michael Sipser demonstrated that constant-depth circuits of the AC⁰ type cannot efficiently compute parity. Johan Håstad sharpened these results through switching lemmas that yield nearly optimal exponential lower bounds for bounded-depth circuits.
For monotone circuits, Alexander Razborov proved superpolynomial lower bounds for explicit graph problems by exploiting the absence of negation. Such results depend on the restricted model and do not automatically extend to general circuits, where negated intermediate values can alter the structure of a computation.
The difficulty of proving general lower bounds is connected to major open questions in complexity theory. A superpolynomial lower bound for circuits computing a language in NP would separate that language from P/poly, although it would not follow merely from the standard statement (P\ne NP). Circuit lower bounds also interact with derandomization, pseudorandom generators, and the distinction between uniform and nonuniform computation.
Physical interpretation
An ideal Boolean circuit treats every signal as exactly zero or one and every gate as an instantaneous function. A physical logic circuit instead represents these values by ranges of voltage or another measurable quantity. Its output changes only after a nonzero propagation delay, and simultaneous input changes may produce temporary values not predicted by the static Boolean function.
These effects motivate timing models that augment the directed graph with delays and electrical constraints. A combinational network is logically correct when its stable outputs agree with the specified Boolean function after transients have settled. Hazards arise when unequal path delays cause an output to change temporarily even though the initial and final logical values are identical.
Despite these physical qualifications, the Boolean circuit remains the principal abstraction for relating logical specification, hardware structure, and nonuniform computation. Its graph records dependency, its gate labels record local operations, and its resource measures support comparisons among alternative realizations of the same function.