3.1 Boolean circuits — hardware as a complexity model

A Boolean circuit with n inputs is a directed acyclic graph whose internal nodes (gates) are labelled AND (∧), OR (∨), NOT (¬), with input nodes x₁...xₙ and one output. Two cost measures:

• Size = number of gates (≈ hardware cost / sequential work)
• Depth = longest input→output path (≈ parallel time!)

A single circuit has a fixed number of inputs, so a problem is solved by a circuit family {Cₙ} — one circuit per input length. This makes circuits a non-uniform model (each size may get its own design, with no requirement that an algorithm generates them — a free "advice" per length).

3.2 Circuits vs Turing machines

Theorem. Any language in TIME(t(n)) has circuits of size O(t(n) log t(n)) — a polynomial-time TM yields polynomial-size circuits. Hence P ⊆ P/poly (poly-size circuit families).

The simulation idea — unroll the computation: a t-step TM computation is a t × t table of cells, each determined by 3 cells of the previous row via a constant gadget of gates. This very table reappears as the heart of the Cook–Levin proof in Unit 3.

Why circuits matter for the big questions: to prove P ≠ NP it would suffice to prove some NP problem needs super-polynomial circuit size. Counting shows almost every Boolean function needs circuits of size ~2ⁿ/n — yet no one can prove any explicit NP problem needs more than ~5n gates. This embarrassing gap (everything is hard, nothing provably so) defines modern lower-bound research.

Small-depth classes worth recognising: NC (poly size, polylog depth — "efficiently parallelisable"), AC⁰ (constant depth, unbounded fan-in). A genuine celebrated lower bound exists here: PARITY ∉ AC⁰ — constant-depth circuits cannot compute parity.

3.3 The Random Access Machine (RAM)

The RAM is the model your algorithms course silently used: an unbounded array of registers, arithmetic on registers, and — the key feature a TM lacks — indirect addressing (access memory cell i in one step, no tape-walking).

Cost models — a subtlety with teeth:

• Unit cost: every operation = 1 step. Realistic only if numbers stay word-sized; with unbounded numbers it cheats (repeated squaring builds 2^(2^t) in t "steps").
• Logarithmic cost: an operation costs the bit-length of its operands. Honest for big-number arithmetic.

Equivalence theorem: TMs and (log-cost) RAMs simulate each other with polynomial overhead. A RAM step touching address a is simulated by a TM walking to a's encoding on tape — O(poly) per step.

Consequence — the one-line exam answer: P, NP, PSPACE etc. are identical whether defined via TMs or RAMs. Theorists prove on TMs (simple), programmers analyse on RAMs (realistic), and the polynomial-equivalence theorem guarantees they are talking about the same classes. Fine distinctions below polynomial (is it n or n log n?) do depend on the model — which is why complexity theory pitches its main definitions at polynomial granularity, where the model noise vanishes.

3.4 A worked circuit design with size/depth accounting

MAJ₃(x₁, x₂, x₃) — output 1 iff at least two inputs are 1:

MAJ₃ = (x₁ ∧ x₂) ∨ (x₁ ∧ x₃) ∨ (x₂ ∧ x₃)

Size: 3 AND gates + 2 OR gates = 5 gates; depth: one AND level then two OR levels = 3 (or 2 with a fan-in-3 OR). The general pattern behind it: any Boolean function of n variables has a DNF circuit of size O(n·2ⁿ) and depth 3 — existence of a circuit is never the issue; size is the entire game.

Shannon's counting argument (1949) — why most functions are hard: there are 2^(2ⁿ) Boolean functions on n inputs, but only about s^O(s) distinct circuits of size s. Setting s ≈ 2ⁿ/(10n) makes s^O(s) smaller than 2^(2ⁿ) — so almost every function requires circuits of size about 2ⁿ/n. Yet the proof names no explicit hard function: it shows hay is everywhere while we cannot exhibit a single straw. Contrast that with §3.2's roughly-5n best known explicit lower bound — that contrast is the lower-bound crisis.

3.5 P/poly and the Karp–Lipton guardrail

P/poly = languages with polynomial-size circuit families (equivalently: poly-time TMs receiving a poly-length advice string that depends only on the input length). Facts to quote:

• P ⊆ P/poly (§3.2), and the inclusion is strict — P/poly even contains undecidable languages! (Take a unary encoding of the halting problem: the one-bit advice for length n can simply be the answer.) Non-uniformity is genuinely alien power.
• Karp–Lipton theorem: if NP ⊆ P/poly, then the polynomial hierarchy collapses to its second level — taken as strong evidence that even tailor-made circuit families cannot solve SAT in polynomial size.
• Consequence for the big picture: since P ⊆ P/poly, proving some NP problem outside P/poly would prove P ≠ NP. This is why circuit lower bounds are considered a credible (if so far stuck) route to the million-dollar question.

3.6 A RAM program under both cost models — the cheat exposed

x = 2
repeat t times:   x = x * x        // after t passes, x = 2^(2^t)

Unit cost: t steps — looks "polynomial". Log cost: the k-th multiplication handles numbers of about 2ᵏ bits, so the honest bill is Σ 2^O(k) = 2^O(t) — exponential, as it must be: the output alone has 2ᵗ bits. Moral for exams: unit cost is legitimate while numbers stay O(log n) bits (array indices, counters); switch to log cost the moment an algorithm builds big numbers, or "polynomial" claims become meaningless.

Exam pointer

Short-note staples: ① "Boolean circuits: size, depth, circuit families, non-uniformity" — §3.1 plus the advice-string sentence; ② "Compare the TM and RAM models" — §3.3's table plus the polynomial-equivalence theorem and its consequence; ③ "Why are circuit lower bounds relevant to P vs NP?" — P ⊆ P/poly, so a super-polynomial circuit bound for an NP problem implies P ≠ NP, and Karp–Lipton makes NP ⊆ P/poly implausible.

Self-check

1. Compute the size and depth of the XNOR circuit drawn in §3.1.
2. What makes a circuit family non-uniform, and what extra requirement makes it uniform? (A poly-time algorithm that outputs Cₙ given 1ⁿ.)
3. State Shannon's counting conclusion in one sentence — and its frustrating caveat.
4. Which class provably cannot compute PARITY: NC or AC⁰?
5. Give the unit-cost and log-cost verdicts for repeated squaring and explain the discrepancy in one sentence.