# P/poly

In computational complexity theory, **P/poly** is the complexity class of languages recognized by a polynomial-time Turing machine with a polynomial-bounded advice function. It is also equivalently defined as the class **PSIZE** of languages that have polynomial-size circuits.^{[1]}^{[2]} This means that the machine that recognizes a language may use a different advice function or use a different circuit depending on the length of the input, and that the advice function or circuit will vary only on the size of the input.

For example, the popular Miller–Rabin primality test can be formulated as a **P/poly** algorithm: the "advice" is a list of candidate *a* values to test. It is possible to precompute a list of at most *n* values such that every composite *n*-bit number will be certain to have a witness *a* in the list. For example, to correctly determine the primality of 32-bit numbers, it is enough to test *a* = 2, 7, and 61.^{[3]} The existence of short lists of candidate witnesses follows from the fact that for each composite *n*, 3/4s of all possible *a* values are witnesses; a simple counting argument similar to the one in the proof that **BPP** in **P/poly** below shows that there *exists* a suitable list of *a* values for every input size, although finding it may be expensive.

**P/poly**, unlike other polynomial-time classes such as **P** or **BPP**, is not generally considered a practical class for computing. Indeed, it contains every undecidable unary language, none of which can be solved in general by real computers. On the other hand, if the input length is bounded by a relatively small number and the advice strings are short, it can be used to model practical algorithms with a separate expensive preprocessing phase and a fast processing phase, as in the example above.

## Contents

## Importance of P/poly[edit]

**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 . This result is the Karp–Lipton theorem; furthermore,**NP**⊆**P/poly**implies**AM**=**MA**^{[4]} - If
**PSPACE**⊆**P/poly**then , 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**.^{[5]}The proof is similar to above, based on an interactive protocol for permanent and #P-completeness of permanent. - If
**EXPTIME**⊆**P/poly**then (Meyer's theorem), even**EXPTIME**=**MA**. - If
**NEXPTIME**⊆**P/poly**then**NEXPTIME**=**EXPTIME**, even**NEXPTIME**=**MA**. Conversely,**NEXPTIME**=**MA**implies**NEXPTIME**⊆**P/poly**^{[6]} - If
**EXP**^{NP}⊆**P/poly**then (Buhrman, Homer)^{[7]} - 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.^{[8]}

## Bounded-error probabilistic polynomial is contained in P/poly[edit]

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**;^{[9]} and this result was generalized to **BPP** ⊆ **P/poly** by Bennett and Gill.^{[10]}
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* 18*n* times (where *n* is the input length and *R* is a sequence of 18*n* independently random *r*s). Thus, *M'* is also polynomial-time, and has an error probability ≤ 1/*e*^{n} by Chernoff's bound (see BPP). If we can fix *R* then we obtain an algorithm that is deterministic.

If Bad(*x*) is defined as {*R*: *M'*(*x*,*R*) is incorrect}, we have:

The input size is *n*, so there are 2^{n} possible inputs. Thus, the probability that a random *R* is bad for at least one input *x* is

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.

## References[edit]

- ^
^{a}^{b}Lutz, Jack H.; Schmidt, William J. (1993), "Circuit size relative to pseudorandom oracles",*Theoretical Computer Science*,**107**(1): 95–119, doi:10.1016/0304-3975(93)90256-S, MR 1201167 **^**Lecture notes on computational complexity by Peter Bro Miltersen**^**Finding primes & proving primality**^**Arvind, Vikraman; Köbler, Johannes; Schöning, Uwe; Schuler, Rainer (1995), "If NP has polynomial-size circuits, then MA = AM",*Theoretical Computer Science*,**137**(2): 279–282, doi:10.1016/0304-3975(95)91133-B, MR 1311226**^**Babai, László; Fortnow, Lance; Lund, Carsten (1991), "Nondeterministic exponential time has two-prover interactive protocols",*Computational Complexity*,**1**(1): 3–40, doi:10.1007/BF01200056, MR 1113533**^**Impagliazzo, Russell; Kabanets, Valentine; Wigderson, Avi (2002), "In search of an easy witness: exponential time vs. probabilistic polynomial time" (PDF),*Journal of Computer and System Sciences*,**65**(4): 672–694, doi:10.1016/S0022-0000(02)00024-7, MR 1964649**^**A Note on the Karp-Lipton Collapse for the Exponential Hierarchy**^**Jin-Yi Cai. Lecture 11: P/poly, Sparse Sets, and Mahaney's Theorem. CS 810: Introduction to Complexity Theory. The University of Wisconsin–Madison. September 18, 2003.**^**Adleman, L. M. (1978), "Two theorems on random polynomial time",*Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computer Science*, pp. 75–83, doi:10.1109/SFCS.1978.37**^**Charles H. Bennett, John Gill.*Relative to a Random Oracle A, P*. [1]^{A}≠ NP^{A}≠ co-NP^{A}with probability 1