8 min read
On this page

Circuit Complexity

Boolean Circuits

A Boolean circuit is a directed acyclic graph where inputs are Boolean variables x_1, ..., x_n, internal nodes are gates (AND, OR, NOT), and designated output nodes produce the result. Key measures:

  • Size: Total number of gates
  • Depth: Length of the longest path from input to output
  • Fan-in: Maximum number of inputs to a gate (bounded or unbounded)

A circuit family {C_n}_{n >= 1} is a sequence of circuits, one for each input length. The family is uniform if there exists a "simple" algorithm to generate C_n from 1^n (e.g., log-space uniform, DLOGTIME-uniform).

Fundamental Circuit Classes

NC (Nick's Class)

NC^k = languages decidable by log-space uniform circuit families of polynomial size and O(log^k n) depth with bounded fan-in (fan-in 2).

NC = union over k of NC^k.

NC captures the class of problems efficiently parallelizable (polylog depth = polylog parallel time with polynomially many processors). NC^1 contains formula evaluation; NC^2 contains deterministic context-free languages.

AC (Alternating Circuits)

AC^k = languages decidable by log-space uniform circuit families of polynomial size and O(log^k n) depth with unbounded fan-in.

The hierarchy: NC^k is contained in AC^k is contained in NC^{k+1}. The first containment is trivial (bounded fan-in is a special case); the second follows because an unbounded fan-in gate of fan-in m can be replaced by a balanced binary tree of depth O(log m) = O(log n).

AC^0 is a fundamental class: constant-depth polynomial-size circuits with unbounded fan-in. AC^0 contains addition, parity check of fixed-weight inputs, and many basic arithmetic operations, but NOT parity of all input bits.

TC (Threshold Circuits)

TC^k = languages decidable by circuit families of polynomial size and O(log^k n) depth using AND, OR, NOT, and threshold gates (output 1 iff at least k inputs are 1).

TC^0 properly contains AC^0 (threshold gates can compute parity). TC^0 captures many arithmetic operations: integer multiplication, division, iterated addition, sorting networks.

Key containments: NC^0 is in AC^0 is in TC^0 is in NC^1 is in L is in NL is in NC^2 is in P.

The separation AC^0 != TC^0 is known (parity). Whether TC^0 = NC^1 is open.

P/poly and Non-Uniform Computation

P/poly = languages decidable by polynomial-size circuit families (no uniformity requirement). Equivalently, P/poly = languages in P with polynomial-length advice strings.

P is contained in P/poly (uniform circuits are a special case). P/poly also contains undecidable languages (the advice can encode non-computable information for each input length).

P/poly and NP: If NP is contained in P/poly, then PH collapses to Sigma_2^P (Karp-Lipton theorem). Thus proving circuit lower bounds for NP would have major structural consequences.

Shannon's Counting Argument

Theorem (Shannon, 1949): Almost all Boolean functions on n variables require circuits of size Omega(2^n / n).

Proof: Count both circuits and functions.

  • Number of Boolean functions on n variables: 2^{2^n}
  • Number of circuits with s gates, each with fan-in 2: at most (c * (n + s))^{2s} for some constant c (each gate chooses its type and two inputs from n variables plus s gate outputs)
  • For s = o(2^n / n), the number of circuits is less than 2^{2^n}, so some function is not computed by any such circuit.

This is a non-constructive existence proof. We cannot explicitly exhibit a function requiring large circuits (doing so for functions in NP would prove P != NP).

The Karp-Lipton Theorem

Theorem (Karp-Lipton, 1982): If NP is contained in P/poly, then PH = Sigma_2^P.

Proof idea: If SAT has polynomial-size circuits, then a Sigma_2^P machine can: (1) existentially guess a circuit C of polynomial size, (2) universally verify that C correctly solves SAT on all relevant inputs. The universal verification uses the self-reducibility of SAT.

Strengthenings:

  • Kobler-Watanabe (1998): If NP is in P/poly, then PH = S_2^P (symmetric alternation).
  • If NEXP is in P/poly, then NEXP = MA (Impagliazzo-Kabanets-Wigderson, 2002).

Circuit Lower Bounds

Parity is Not in AC^0

Theorem (Furst-Saxe-Sipser, 1984; Ajtai, 1983): The parity function is not in AC^0. Any constant-depth circuit computing parity requires exponential size (2^{n^{Omega(1/d)}} for depth d).

Hastad's switching lemma provides the strongest quantitative bounds.

Hastad's Switching Lemma

Lemma (Hastad, 1986): Let f be a DNF (or CNF) where each term has width at most t. Under a random restriction rho that fixes each variable independently with probability 1 - p, the probability that f restricted by rho cannot be written as a CNF (or DNF) of width at most s is at most (5pt)^s.

Application: A depth-d circuit of size S computing parity can be hit with d-1 rounds of random restrictions. Each round reduces the depth by 1 (switching between CNF and DNF) and shrinks the width. After d-1 rounds, the circuit becomes a constant, but parity remains non-trivial with high probability if S < 2^{n^{Omega(1/d)}}. Contradiction.

This gives: any AC^0 circuit for parity on n bits of depth d requires size at least 2^{Omega(n^{1/(d-1)})}.

Razborov's Monotone Circuit Lower Bounds

Theorem (Razborov, 1985): The clique function (does a graph on n vertices contain a k-clique?) requires monotone circuits of size n^{Omega(k)} for k <= n^{1/4}.

Method of approximations: Replace each gate's function with a simpler "approximation" from a restricted class. Show that:

  1. Approximations of small circuits remain close to the original function
  2. No approximation in the restricted class can compute the clique function
  3. The error introduced per gate is small enough that the accumulated error is bounded

Corollary: Monotone circuits for the clique function require superpolynomial (in fact, quasi-exponential) size.

Limitation: Razborov-Alekhnovich showed that monotone lower bounds do not generally imply non-monotone lower bounds. The negation gates can provide exponential savings for some functions.

The Natural Proofs Barrier

Theorem (Razborov-Rudich, 1997): If one-way functions exist, then no natural property can prove superpolynomial circuit lower bounds for functions in P/poly.

A proof is natural if it identifies a property of truth tables that is:

  1. Constructive: Testable in time 2^{O(n)} given the truth table
  2. Large: Satisfied by a random function with non-negligible probability
  3. Useful: Not satisfied by any function with small circuits

Both the switching lemma and Razborov's method are natural. To prove P != NP via circuits, non-natural methods are needed (or one-way functions do not exist, which would itself resolve major problems).

Circuit Complexity and Complexity Classes

| Circuit Class | Uniform Analog | Key Property | |---|---|---| | AC^0 | FO (first-order logic) | Constant depth, unbounded fan-in | | TC^0 | FOM (FO + majority) | Threshold gates | | NC^1 | ALOGTIME | Bounded fan-in, log depth | | NC^2 | -- | Log^2 depth | | P/poly | P + advice | Polynomial size, non-uniform |

ACC and the ACC^0 Lower Bound

ACC^0 extends AC^0 with MOD_m gates (output 1 iff the number of true inputs is 0 mod m).

Theorem (Williams, 2011): NEXP is not in ACC^0. This is the strongest known circuit lower bound for an explicit uniform class.

Williams' proof uses a surprising connection: sufficiently fast satisfiability algorithms for ACC^0 circuits imply lower bounds against ACC^0. The proof is non-constructive in spirit, using the contrapositive (if NEXP were in ACC^0, we could solve ACC^0-SAT too quickly, contradicting the time hierarchy).

Algebraic Circuit Connections

  • Valiant's theorem: The permanent is #P-hard, and computing it requires large arithmetic circuits under Valiant's conjecture (VP != VNP).
  • Polynomial identity testing (PIT): Deterministic PIT in polynomial time would yield circuit lower bounds (Kabanets-Impagliazzo, 2004).

Branching Programs

Branching programs are a non-uniform model related to space complexity:

  • Width-5 branching programs capture exactly NL (Barrington's theorem, 1989): Any language in NC^1 (equivalently, any language computed by polynomial-size formulas) can be computed by polynomial-length, width-5 branching programs.
  • Read-once branching programs (OBDDs) are a restricted model where each variable is queried at most once on any path.

Theorem (Barrington, 1989): NC^1 = width-5 polynomial-length branching programs.

The proof uses the fact that the symmetric group S_5 is non-solvable, allowing simulation of AND gates via group commutators.

Lower Bound Frontier

The strongest known lower bounds for explicit functions:

  • AC^0: Exponential (parity, Hastad)
  • AC^0[p] for prime p: Exponential for MOD_q, q != p (Razborov, Smolensky)
  • ACC^0: NEXP not in ACC^0 (Williams)
  • TC^0: No superlinear lower bounds known
  • General circuits: Best known is 5n - o(n) (Iwama et al.), barely superlinear

The gap between our lower bounds (slightly superlinear for general circuits) and what we believe (P != NP implies NP requires 2^{n^{Omega(1)}} size circuits) represents one of the biggest challenges in complexity theory.

Open Problems

  • Prove superpolynomial circuit lower bounds for a language in NP (this would prove P != NP)
  • Is TC^0 = NC^1?
  • Can monotone lower bounds be extended to non-monotone circuits?
  • Does P/poly contain NP? (Believed no, but equivalent to P vs NP for uniform classes)
  • Can Williams' NEXP lower bound be improved to NEXP not in TC^0?