Circuit Complexity
Circuit complexity measures the size and depth of Boolean circuits needed to compute a function, offering a hardware-based view of difficulty.
Computation as circuits
A Boolean circuit is a network of AND, OR, and NOT gates wired to compute a function of its input bits. Circuit complexity studies how large (number of gates) and how deep (longest path from input to output) a circuit must be to compute a given function. It is an alternative to the time-and-tape view of complexity.
Size and depth
- Size: total gate count, corresponding roughly to total work
- Depth: longest input-to-output path, corresponding to parallel time
- Fan-in: how many inputs each gate may take
Why depth matters
Depth measures how fast a function can be computed in parallel: gates at the same depth level can fire simultaneously. Low-depth circuits capture highly parallelizable computations. The class NC contains problems solvable by circuits of polynomial size and polylogarithmic depth, the theoretical model of efficient parallelism.
Uniform versus non-uniform
A single circuit handles one input size, so a family of circuits, one per size, is needed for a full problem. If a machine can generate the circuit for each size efficiently, the family is uniform. Non-uniform families are more powerful and can even compute some undecidable functions, since each circuit is allowed to hard-wire answers.
Lower bounds and P vs NP
Proving that some NP problem needs superpolynomial circuit size would show P is not NP. Circuit lower bounds are a leading attack on the question, and strong bounds are known for restricted circuit classes, but general lower bounds remain out of reach, blocked by the natural-proofs barrier.
The connection to P
A problem is in P if and only if it has a uniform family of polynomial-size circuits. This equivalence lets researchers translate questions about time complexity into questions about circuits, where combinatorial and algebraic tools sometimes give more traction.