The complexity class P/poly can be defined in terms of SIZE as follows:

${\displaystyle {\mathsf {P/poly}}=\cup _{c\in \mathbb {N} }{\mathsf {SIZE}}(n^{c}).}$ 

where ${\displaystyle {\mathsf {SIZE}}(n^{c})}$  is the set of decision problems that can be solved by polynomial-sized circuit families.

Alternatively, ${\displaystyle {\mathsf {P/poly}}}$  can be defined using Turing machines that "take advice". Such a machine has, for each n, an advice string ${\displaystyle \alpha _{n}}$ , which it is allowed to use in its computation whenever the input has size n.

Let ${\displaystyle T,a:\mathbb {N} \rightarrow \mathbb {N} }$  be functions. The class of languages decidable by time-T(n) Turing machines with ${\displaystyle a(n)}$  advice, denoted ${\displaystyle {\mathsf {DTIME}}(T(n))/a(n)}$ , contains every language L such that there exists a sequence ${\displaystyle \{\alpha _{n}\}_{n\in \mathbb {N} }}$  of strings with ${\displaystyle \alpha _{n}\in \{0,1\}^{a(n)}}$  and a TM M satisfying

${\displaystyle M(x,\alpha _{n})=1\Leftrightarrow x\in L}$ 

for every ${\displaystyle x\in \{0,1\}^{n}}$ , where on input ${\displaystyle (x,\alpha _{n})}$  the machine M runs for at most ${\displaystyle O(T(n))}$  steps.^[6]

P/poly is an important class for several reasons. For theoretical computer science, there are several important properties that depend on P/poly:

• If NP ⊆ P/poly then PH (the polynomial hierarchy) collapses to ${\displaystyle \Sigma _{2}^{\mathsf {P}}}$ . This result is the Karp–Lipton theorem; furthermore, NP ⊆ P/poly implies AM = MA ^[7]
• If PSPACE ⊆ P/poly then ${\displaystyle {\mathsf {PSPACE}}=\Sigma _{2}^{\mathsf {P}}\cap \Pi _{2}^{\mathsf {P}}}$ , even PSPACE = MA.

Proof: Consider a language L from PSPACE. It is known that there exists an interactive proof system for L, where actions of the prover can be carried out by a PSPACE machine. By assumption, the prover can be replaced by a polynomial-size circuit. Therefore, L has a MA protocol: Merlin sends the circuit as proof, and Arthur can simulate the IP protocol himself without any additional help.

• If P^#P ⊆ P/poly then P^#P = MA.^[8] The proof is similar to above, based on an interactive protocol for permanent and #P-completeness of permanent.
• If EXPTIME ⊆ P/poly then ${\displaystyle {\mathsf {EXPTIME}}=\Sigma _{2}^{\mathsf {P}}\cap \Pi _{2}^{\mathsf {P}}}$  (Meyer's theorem), even EXPTIME = MA.
• If NEXPTIME ⊆ P/poly then NEXPTIME = EXPTIME, even NEXPTIME = MA. Conversely, NEXPTIME = MA implies NEXPTIME ⊆ P/poly^[9]
• If EXP^NP ⊆ P/poly then ${\displaystyle {\mathsf {EXP^{NP}}}=\Sigma _{2}^{\mathsf {P}}\cap \Pi _{2}^{\mathsf {P}}}$  (Buhrman, Homer) ^[10]
• It is known that MA_EXP, an exponential version of MA, is not contained in P/poly.

Proof: If MA_EXP ⊆ P/poly then PSPACE = MA (see above). By padding, EXPSPACE = MA_EXP, therefore EXPSPACE ⊆ P/poly but this can be proven false with diagonalization.

One of the most interesting reasons that P/poly is important is the property that if NP is not a subset of P/poly, then P ≠ NP. This observation was the center of many attempts to prove P ≠ NP. It is known that for a random oracle A, NP^A is not a subset of P^A/poly with probability 1.^[1]

P/poly is also used in the field of cryptography. Security is often defined 'against' P/poly adversaries. Besides including most practical models of computation like BPP, this also admits the possibility that adversaries can do heavy precomputation for inputs up to a certain length, as in the construction of rainbow tables.

Although not all languages in P/poly are sparse languages, there is a polynomial-time Turing reduction from any language in P/poly to a sparse language.^[11]

Adleman's theorem states that BPP ⊆ P/poly, where BPP is the set of problems solvable with randomized algorithms with two-sided error in polynomial time. A weaker result was initially proven by Leonard Adleman, namely, that RP ⊆ P/poly;^[12] and this result was generalized to BPP ⊆ P/poly by Bennett and Gill.^[13] Variants of the theorem show that BPL is contained in L/poly and AM is contained in NP/poly.

Proof edit

Let L be a language in BPP, and let M(x,r) be a polynomial-time algorithm that decides L with error ≤ 1/3 (where x is the input string and r is a set of random bits).

Construct a new machine M'(x,R), which runs M 48n times and takes a majority vote of the results (where n is the input length and R is a sequence of 48n independently random rs). Thus, M' is also polynomial-time, and has an error probability ≤ 1/eⁿ by the Chernoff bound (see BPP). If we can fix R then we obtain an algorithm that is deterministic.

If ${\displaystyle {\mbox{Bad}}(x)}$  is defined as ${\displaystyle \{R:M{'}(x,R){\text{ is incorrect}}\}}$ , we have:

${\displaystyle \forall x\,{\mbox{Prob}}_{R}[R\in {\mbox{Bad}}(x)]\leq {\frac {1}{e^{n}}}.}$ 

The input size is n, so there are 2ⁿ possible inputs. Thus, by the union bound, the probability that a random R is bad for at least one input x is

${\displaystyle {\mbox{Prob}}_{R}[\exists x\,R\in {\mbox{Bad}}(x)]\leq {\frac {2^{n}}{e^{n}}}<1.}$ 

In words, the probability that R is bad for some x is less than 1, therefore there must be an R that is good for all x. Take such an R to be the advice string in our P/poly algorithm.