Boolean Circuits & P/poly

Nonuniform circuits, size and depth, and the class P/poly.

The idea

A Boolean circuit is a fixed-size model of computation, and $\mathsf{P}/\mathrm{poly}$ is the class of languages decided by small circuits. A circuit on $n$ inputs is a directed acyclic graph whose nodes are $\wedge$, $\vee$, and $\neg$ gates, wired from $n$ input nodes $x_{1}, \ldots, x_{n}$ to a single output; it computes one function $f \colon \{0,1\}^{n} \to \{0,1\}$, for one input length only. A language contains strings of every length, so deciding one requires a family $\{C_{n}\}_{n \ge 0}$, one circuit per length.

The family is nonuniform: no single algorithm is required to produce its circuits — this is the departure from the Turing machine, which is one device handling every input length. We charge a family by its size, the number of gates, and its depth, the longest path from an input to the output, and define $\mathsf{P}/\mathrm{poly} = \{\,\text{languages decided by a circuit family of size } n^{O(1)}\,\}.$

Because the circuits need not be describable by any algorithm, the class is generous — it contains languages no algorithm decides at all. Its value lies in the other direction: a circuit is a finite combinatorial object with nothing hidden inside it, which makes it the natural setting for proving lower bounds.

Ways to work on it

• Walkthrough. Circuit families, size and depth, and why P sits inside P/poly.
• Practice. Count functions, inputs, or gates for circuits on a fixed input length.
• Hardest. Show that most Boolean functions need exponential-size circuits.

Not sure where to start? Take the ten-question placement test.