How do circuits differ from Turing machines?

A Turing machine is a single device handling inputs of all sizes step by step, while a circuit is a fixed network of gates for one input length, with a separate circuit for each length. This non-uniformity makes circuits a natural model of hardware and of parallel computation, and it can express things no single uniform machine does.

Why do researchers care about circuit lower bounds?

Proving that a problem in NP requires very large circuits would separate complexity classes and could resolve P versus NP. Lower bounds are known for restricted circuit families, but extending them to general circuits is blocked by formal barriers, making this one of the deepest open challenges in the field.

Boolean Circuits and Circuit Complexity

Boolean circuits compute functions through networks of logic gates, and circuit complexity measures problems by the size and depth of the circuits needed to solve them, offering a parallel and hardware-oriented view of computation.

Definition

A Boolean circuit is a directed acyclic graph of logic gates computing a function of fixed-length binary inputs; circuit complexity studies the minimal number of gates, the depth, or other structural resources required to compute a given family of Boolean functions.

Scope

This topic covers Boolean circuits and formulas, the size and depth measures of complexity, uniform versus non-uniform models, low-depth classes such as NC and AC, the relationship between circuit lower bounds and the separation of complexity classes, and landmark lower-bound results for restricted circuit families.

Core questions

How does the gate-network view of computation differ from sequential machines?
What do circuit size and depth measure, and how do they relate to time and parallelism?
Why are circuit lower bounds a route toward separating complexity classes?
What lower bounds are known, and what barriers block stronger ones?

Key theories

Non-uniformity and the class P/poly: Circuits allow a different machine for each input length, giving the non-uniform class P/poly that contains P; showing an NP-complete problem lacks polynomial-size circuits would separate P from NP, motivating circuit lower bounds.
Lower bounds for restricted circuits: Strong lower bounds are known for limited families, such as the exponential size required for constant-depth circuits computing parity, even though lower bounds for general circuits remain out of reach.

Clinical relevance

Circuits are the natural model of digital hardware, so circuit complexity informs chip design and the limits of parallel computation; the low-depth classes capture what can be computed quickly with many processors, and circuit lower bounds are a principal strategy in the long-term effort to resolve questions like P versus NP.

History

Shannon connected Boolean algebra to switching circuits in 1937, and circuit complexity matured as a discipline in the 1980s when Furst, Saxe, Sipser, and others proved constant-depth lower bounds for parity, and Razborov and Smolensky developed algebraic methods, before the natural-proofs barrier revealed why general lower bounds are so elusive.

Key figures

Claude Shannon
Alexander Razborov
Andrew Yao
Roman Smolensky

Seminal works

aroraBarak2009
vollmer1999

Frequently asked questions

How do circuits differ from Turing machines?: A Turing machine is a single device handling inputs of all sizes step by step, while a circuit is a fixed network of gates for one input length, with a separate circuit for each length. This non-uniformity makes circuits a natural model of hardware and of parallel computation, and it can express things no single uniform machine does.
Why do researchers care about circuit lower bounds?: Proving that a problem in NP requires very large circuits would separate complexity classes and could resolve P versus NP. Lower bounds are known for restricted circuit families, but extending them to general circuits is blocked by formal barriers, making this one of the deepest open challenges in the field.