Computation drawn as a graph of gates. A circuit is a DAG whose sources are input bits and whose interior nodes are AND, OR, NOT; two numbers describe it — SIZE (how many gates, the sequential work) and DEPTH (longest path, the parallel time). Shannon's 1938 thesis showed the wiring of a relay panel is Boolean algebra. Down the center, a target function goes in, a circuit is built and verified against its whole truth table, and the proven result comes out. The blue team builds it; the red team breaks it.
source Shannon, A Symbolic Analysis of Relay and Switching Circuits, Trans. AIEE 57 (1938) 713–723 — DOI 10.1109/T-AIEE.1938.5057767. Rendered, not quoted.
A circuit is a list of gates in DAG order: every gate reads only from gates before it. Two measures fall straight out of the graph:
SIZE = number of non-input gates (the sequential work). DEPTH = longest path from an input to the output (the parallel time — the number of layers even infinite parallelism must wait through).
Live, for the circuit in the panel:
Shannon's move: a switch is a variable, series is AND, parallel is OR, a break-contact is NOT. A relay network became an expression in the algebra of 0 and 1.
Turn the expression into a graph and you have a complexity model: circuit families are the P/poly world sitting underneath the-turing-machine — same computation, measured in gates and layers instead of tape steps. Each sphere is the next one's premise.
The blue team's live check: rebuild the MAJ3 reference circuit, recompute its whole truth table, and confirm it against the independently-computed majority function — plus a DNF round-trip. If red tampers, this badge is where it shows.
The input is a Boolean function: for every one of the 2n input patterns, one output bit. That is the truth table below — click any output cell to flip it. Three gate types build everything:
| gate | rule |
|---|---|
| AND | 1 only if both inputs are 1 (series switches) |
| OR | 1 if either input is 1 (parallel switches) |
| NOT | flips the bit (a break-contact) |
A wire may fan out to many gates but never loops back — the graph is acyclic. That table is what you feed the panel below.
The builder realizes any function you set as a DNF circuit — one AND-term per 1-row (a minterm of n literals), all OR-ed together. Every function is realizable; the cost is size O(n·2n).
Flip any bit — the circuit is rebuilt and re-verified against the full truth table on the spot, never looked up.
What the machine produces, proven: a circuit that reproduces the target on all 2n rows (exact truth-table match), with its SIZE and DEPTH measured from the graph. Because the DNF construction works for every table, this is a live proof that every Boolean function is realizable by a circuit. Parity's small circuit vs its exponential DNF shows why SIZE, not mere realizability, is the real question.
The blue team's witness (left) confirms the reference live; the red team (right) tries to make a circuit compute the wrong function.
Worse, circuits are non-uniform — a different circuit per length n, chosen with hindsight. A circuit family can even decide undecidable languages by taking one bit of advice per length. So raw circuit size is only a fair model once you demand the family be uniformly generated.
"Every Boolean function has a small circuit." Cut. Shannon 1949: almost all functions need size ~2n/n. Only structured functions are cheap.
"Circuits equal Turing machines in power." Cut. Non-uniform families are strictly stronger (advice decides undecidable sets); equivalence needs a uniform family and holds only up to polynomial overhead.
"DNF is the efficient form." Kept, corrected. DNF always works but can blow up: parity needs 2n−1 minterms as a DNF, yet a linear-size XOR-chain circuit computes it.
The red team's move: reach into the MAJ3 reference circuit and flip its final OR into an AND. Now it computes the wrong function on at least one input. The blue team's witness (window 7) is watching.
Flip the output gate and the majority circuit computes AND-of-pairs instead — it disagrees with the true majority on input a=b=1, c=0. The witness recomputes the full truth table, catches the mismatch, and turns red. Nothing is faked; the attack is real and it is caught.