P/poly

The class of decision problems solvable by polynomial-size Boolean circuits — equivalently, by a polynomial-time Turing machine with access to a polynomial-length advice string that depends only on the input length (not on the particular input). Formally, a language $L\in P/poly$ if there exist polynomials $p,q$ and a polynomial-time algorithm $A$ such that for every input length $n$, there is an advice string $a_n\in \{0,1{\}}^{q(n)}$ with

$$x\in L⟺A(x,a_n)=1\text{for all }x\in \{0,1{\}}^n.$$

P/poly is a non-uniform class: the “algorithm” (circuit) can be different for each input length, and is not required to be uniformly generated.

See the complexity zoo entry here.

Known relationships

• $\mathbf{P}\subseteq P/poly$: any uniform polynomial-time algorithm is also a polynomial-size circuit family.
• $\mathbf{BPP}\subseteq P/poly$: under the standard derandomization assumption (that $\mathbf{E}$ requires exponential-size circuits), $\mathbf{BPP}=\mathbf{P}$. Unconditionally, by a probabilistic argument, BPP $\subseteq$ P/poly — the advice string encodes a fixed set of random coins that works for all inputs of a given length — Adl78 ($\mathbf{RP}$ case), BG81 ($\mathbf{BPP}$); see bpp-to-p-poly.
• Karp-Lipton theorem: if $\mathbf{NP}\subseteq P/poly$, then the polynomial hierarchy collapses to ${\mathbf{\Sigma }}_2^{\mathbf{P}}={\mathbf{\Pi }}_2^{\mathbf{P}}$ — KL80. Proof idea: for a ${\Pi }_2$ statement $\forall y\exists z\varphi (x,y,z)$, existentially guess a polynomial-size circuit $C$ that outputs a witness $z$ whenever one exists (it exists by self-reducibility of SAT), then universally check $\varphi (x,y,C(x,y))$.
• $P/poly$ contains undecidable languages: every unary language is in $P/poly$ (one advice bit per input length), including the unary encoding of the halting problem — folklore.

Relevance to cryptography

Non-uniform security is the standard model in modern cryptography. When we say a scheme is secure against all polynomial-time adversaries, we typically mean against all polynomial-size circuits (P/poly adversaries), not just uniform PPT algorithms. This matters because:

• Security reductions are often stated in the non-uniform setting.
• One-way functions secure against non-uniform adversaries imply $\mathbf{NP}⊈P/poly$, since inverting a one-way function is an $\mathbf{NP}$ search problem — folklore.
• PRG constructions that fool $P/poly$ are strictly stronger than those that fool only uniform algorithms.

Participates in

Produces P/poly

• poly
• poly