# P/poly

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/P/poly
> Markdown URL: https://mediated.wiki/source/P/poly.md
> Source: https://en.wikipedia.org/wiki/P%2Fpoly
> Source revision: 1333817893
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In [computational complexity theory](/source/Computational_complexity_theory), **P/poly** is a [complexity class](/source/Complexity_class) that can be defined in both [circuit complexity](/source/Circuit_complexity) and [non-uniform complexity](/source/Circuit_complexity#Uniformity). Since the two definitions are equivalent, this concept bridges the two areas.

In the perspective of circuit complexity, **P/poly** is the class of problems that can be solved by small circuits. More precisely, it is the set of [formal languages](/source/Formal_language) that have polynomial-size circuit families.

In the perspective of non-uniform complexity, **P/poly** is defined in terms of [Turing machines](/source/Turing_machine) with [advice](/source/Advice_(complexity)), extra information supplied to the Turing machine along with its input, that may depend on the input length but not on the input itself. In this formulation, **P/poly** is the class of [decision problems](/source/Decision_problem) that can be solved by a polynomial-time [Turing machine](/source/Turing_machine) with advice strings of length polynomial in the input size.[1][2]

For example, the popular [Miller–Rabin primality test](/source/Miller%E2%80%93Rabin_primality_test) can be formulated as a **P/poly** algorithm: the "advice" is a list of candidate values to test. It is possible to precompute a list of O(n) values such that every composite n-bit number will be certain to have a witness a in the list.[3] For example, to correctly determine the primality of 32-bit numbers, it is enough to test a\in\{2,7,61\}.[4][5] The existence of short lists of candidate witnesses follows from the fact that for each composite n, three out of four candidate values successfully detect that n is composite. From this, a simple counting argument similar to the one in the proof that \mathsf{BPP} \subset \mathsf{P/poly} below shows that there exists a suitable list of candidate values for every input size, and more strongly that most long-enough lists of candidate values will work correctly, although finding a list that is guaranteed to work may be expensive.[3]

**P/poly**, unlike other polynomial-time classes such as **[P](/source/P_(complexity))** or **[BPP](/source/Bounded-error_probabilistic_polynomial)**, is not generally considered a practical class for computing. Indeed, it contains every [undecidable](/source/Undecidable_problem) [unary language](/source/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 Miller–Rabin example.

## Formal definition

The [complexity class](/source/Complexity_class) **P/poly** can be defined in terms of **SIZE** as follows:

- \mathsf{P/poly} = \bigcup_{c\in\mathbb{N}} \mathsf{SIZE}(n^c),

where \mathsf{SIZE}(n^c) is the set of [decision problems](/source/Decision_problem) that can be solved by circuit families having no more than n^c gates on inputs of size n.

Alternatively, \mathsf{P/poly} can be defined using [Turing machines](/source/Turing_machine) that "take advice". Such a machine has, for each n, an *[advice string](/source/Advice_(complexity))* \alpha_n, which it is allowed to use in its computation whenever the input has size n. To help visualize this equivalence, imagine that the advice for each n is a description of a Boolean circuit having n inputs, and that a Turing Machine for the language merely evaluates the given Boolean circuit on inputs of length n.

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

- M(x, \alpha_n) = 1 \Leftrightarrow x \in L

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

## Importance of P/poly

**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](/source/NP_(complexity))** ⊆ **P/poly** then **PH** (the [polynomial hierarchy](/source/Polynomial_hierarchy)) collapses to \Sigma_2^{\mathsf P}. This result is the [Karp–Lipton theorem](/source/Karp%E2%80%93Lipton_theorem); furthermore, **NP** ⊆ **P/poly** implies **[AM](/source/Arthur%E2%80%93Merlin_protocol)** = **MA** [7]
- If **[PSPACE](/source/PSPACE)** ⊆ **P/poly** then \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](/source/IP_(complexity)) 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](/source/Sharp_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](/source/Permanent_is_sharp-P-complete).
- If **[EXPTIME](/source/EXPTIME)** ⊆ **P/poly** then \mathsf{EXPTIME} =\Sigma_2^{\mathsf P} \cap \Pi_2^{\mathsf P} (Meyer's theorem), even **EXPTIME** = **MA**.
- If **[NEXPTIME](/source/NEXPTIME)** ⊆ **P/poly** then **NEXPTIME** = **EXPTIME**, even **NEXPTIME** = **MA**. Conversely, **NEXPTIME** = **MA** implies **NEXPTIME** ⊆ **P/poly**[9]
- If **EXP****NP** ⊆ **P/poly** then \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](/source/Arthur%E2%80%93Merlin_protocol)**, is not contained in **P/poly**.

- Proof: If **MA**EXP ⊆ **P/poly** then **PSPACE** = **MA** (see above). By [padding](/source/Padding_argument), **EXPSPACE** = **MA**EXP, therefore **EXPSPACE** ⊆ **P/poly** but this can be proven false with diagonalization.

- The best known bound for the [square-root sum problem](/source/Square-root_sum_problem) is in the fourth level of the counting hierarchy, and it is an unsolved problem whether better complexity is possible, but a unary version of the problem is in **P/poly**.[11]

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](/source/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](/source/Rainbow_table).

Although not all languages in **P/poly** are [sparse languages](/source/Sparse_language), there is a [polynomial-time Turing reduction](/source/Polynomial-time_Turing_reduction) from any language in **P/poly** to a sparse language.[12]

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

Adleman's theorem states that **[BPP](/source/Bounded-error_probabilistic_polynomial)** ⊆ **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](/source/Leonard_Adleman), namely, that **[RP](/source/RP_(complexity))** ⊆ **P/poly**;[13] and this result was generalized to **BPP** ⊆ **P/poly** by [Bennett](/source/Charles_H._Bennett_(computer_scientist)) and Gill.[14] Variants of the theorem show that **[BPL](/source/BPL_(complexity))** is contained in **[L/poly](/source/L/poly)** and **AM** is contained in **[NP/poly](/source/NP/poly)**.

### Proof

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 *′*(*x*,*R*), which runs *M* 48*n* times and takes a majority vote of the results (where *n* is the input length and *R* is a sequence of 48*n* independently random *r*s). Thus, *′* is also polynomial-time, and has an error probability ≤ 1/*e**n* by the [Chernoff bound](/source/Chernoff_bound) (see [BPP](/source/Bounded-error_probabilistic_polynomial)). If we can fix *R* then we obtain an algorithm that is deterministic.

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

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

The input size is *n*, so there are 2*n* possible inputs. Thus, by the [union bound](/source/Union_bound), the probability that a random *R* is bad for at least one input *x* is

- \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 at least one *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

1. Lutz, Jack H. & Schmidt, William J. (1993), "Circuit size relative to pseudorandom oracles", *[Theoretical Computer Science](/source/Theoretical_Computer_Science_(journal))*. **107** (1): 95–119, [doi:10.1016/0304-3975(93)90256-S](https://doi.org/10.1016/0304-3975(93)90256-S). MR 1201167

1. ["Lecture notes on computational complexity by Peter Bro Miltersen"](https://web.archive.org/web/20120223150858/http://www.daimi.au.dk/~bromille/CT06/complex3.pdf), archived from [the original](http://www.daimi.au.dk/~bromille/CT06/complex3.pdf) on 2012-02-23, retrieved 2009-12-25

1. Goldreich, Oded & Wigderson, Avi (2002), "Derandomization that is rarely wrong from short advice that is typically good", "Randomization and Approximation Techniques, 6th International Workshop, RANDOM 2002, Cambridge, MA, USA, September 13-15, 2002, Proceedings", Vol. 2483, Lecture Notes in Computer Science, Springer, pp. 209–223, [doi:10.1007/3-540-45726-7_17](https://doi.org/10.1007/3-540-45726-7_17)

1. Caldwell, Chris, ["2.3: Strong probable-primality and a practical test"](http://primes.utm.edu/prove/prove2_3.html), *Finding primes & proving primality*

1. Jaeschke, Gerhard (1993), "On strong pseudoprimes to several bases", *Mathematics of Computation*. **61** (204): 915–926, [doi:10.2307/2153262](https://doi.org/10.2307/2153262). MR 1192971; see p. 926.

1. Arora, Sanjeev & Barak, Boaz (2009), *Computational complexity. A modern approach*, [Cambridge University Press](/source/Cambridge_University_Press), ISBN 978-0-521-42426-4. Zbl 1193.68112

1. Arvind, Vikraman; Köbler, Johannes; Schöning, Uwe; Schuler, Rainer (1995), ["If NP has polynomial-size circuits, then MA = AM"](http://www.informatik.hu-berlin.de/forschung/gebiete/algorithmenII/Publikationen/Papers/ma-am.ps.gz), *[Theoretical Computer Science](/source/Theoretical_Computer_Science_(journal))*. **137** (2): 279–282, [doi:10.1016/0304-3975(95)91133-B](https://doi.org/10.1016/0304-3975(95)91133-B). MR 1311226

1. Babai, László; Fortnow, Lance; Lund, Carsten (1991), ["Nondeterministic exponential time has two-prover interactive protocols"](https://web.archive.org/web/20120331215832/http://www.cs.uchicago.edu/files/tr_authentic/TR-91-10.ps), *Computational Complexity*. **1** (1): 3–40, [doi:10.1007/BF01200056](https://doi.org/10.1007/BF01200056). MR 1113533, archived from [the original](http://www.cs.uchicago.edu/files/tr_authentic/TR-91-10.ps) on 2012-03-31, retrieved 2011-10-02

1. Impagliazzo, Russell; Kabanets, Valentine; Wigderson, Avi (2002), ["In search of an easy witness: exponential time vs. probabilistic polynomial time"](http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IKW02/IKW02.pdf), *[Journal of Computer and System Sciences](/source/Journal_of_Computer_and_System_Sciences)*. **65** (4): 672–694, [doi:10.1016/S0022-0000(02)00024-7](https://doi.org/10.1016/S0022-0000(02)00024-7). MR 1964649

1. [A Note on the Karp-Lipton Collapse for the Exponential Hierarchy](http://cse.unl.edu/~cbourke/pubs/EXPnote.pdf)

1. Balaji, Nikhil & Datta, Samir (2024), "USSR is in P/poly", "2024 Symposium on Simplicity in Algorithms, SOSA 2024, Alexandria, VA, USA, January 8-10, 2024", {SIAM}, pp. 151–159, [arXiv:2310.19335](https://arxiv.org/abs/2310.19335). [doi:10.1137/1.9781611977936.15](https://doi.org/10.1137/1.9781611977936.15)

1. Jin-Yi Cai. [Lecture 11: P/poly, Sparse Sets, and Mahaney's Theorem](http://pages.cs.wisc.edu/~jyc/02-810notes/lecture11.pdf). CS 810: Introduction to Complexity Theory. The University of Wisconsin–Madison. September 18, 2003.

1. 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](https://doi.org/10.1109/SFCS.1978.37)

1. Charles H. Bennett, John Gill. *Relative to a Random Oracle A, PA ≠ NPA ≠ co-NPA with probability 1*. [\[1\]](https://www.cs.cornell.edu/courses/cs682/2006sp/handouts/bennettgill.pdf)

---
Adapted from the Wikipedia article [P/poly](https://en.wikipedia.org/wiki/P%2Fpoly) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/P%2Fpoly?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.