Circuit family

A circuit family $(C_n)$ contains one circuit for each input length $n$. The circuit for one length may be chosen independently of those for other lengths, so a family is a nonuniform model of computation.

The languages whose length-$n$ indicator functions have Boolean circuits with at most $T(n)$ gates for sufficiently large $n$, over a fixed bounded-fan-in complete basis. The family need not be constructible by one algorithm. Polynomial-size bounds give P/poly; the truth-table upper bound for circuit size applies even to undecidable languages.

OR together one minterm for each accepted length-$n$ input. Each minterm is an AND of the appropriate Boolean literals. There are at most $2^n$ minterms, and their negated input wires can be shared, giving $O(n{2}^n)$ bounded-fan-in gates. This is a nonuniform existence statement, not an algorithm for determining an undecidable truth table.

A circuit family has polynomial size when $C_n$ has at most $n^{O(1)}$ gates.

For any set of lengths $A$, choose at length $n$ a constant-zero Boolean circuit when $n\notin A$, and an AND of all inputs when $n\in A$. This uses $O(n+1)$ gates. If $A$ is undecidable, so is $U_A$, yet it belongs to P/poly. Since all NP languages are decidable by certificate enumeration, this proves P/poly is not equal to NP; it does not resolve containment in the other direction.

$\mathbf{P}/\mathrm{poly}$ is the class of decision problems decided by polynomial-size circuit families.