P/poly

In computational complexity theory, P/poly is a complexity class that can be defined in both circuit complexity and non-uniform complexity. 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 that have polynomial-size circuit families.
In the perspective of non-uniform complexity, P/poly is defined in terms of Turing machines with advice, 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 that can be solved by a polynomial-time Turing machine with advice strings of length polynomial in the input size.
For example, the popular Miller–Rabin 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 values such that every composite -bit number will be certain to have a witness in the list. For example, to correctly determine the primality of 32-bit numbers, it is enough to test. The existence of short lists of candidate witnesses follows from the fact that for each composite, three out of four candidate values successfully detect that is composite. From this, a simple counting argument similar to the one in the proof that 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.
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 Miller–Rabin example.

Formal definition

The complexity class P/poly can be defined in terms of SIZE as follows:
where is the set of decision problems that can be solved by circuit families having no more than gates on inputs of size.
Alternatively, can be defined using Turing machines that "take advice". Such a machine has, for each, an advice string, which it is allowed to use in its computation whenever the input has size. To help visualize this equivalence, imagine that the advice for each is a description of a Boolean circuit having inputs, and that a Turing Machine for the language merely evaluates the given Boolean circuit on inputs of length.
Let be functions. The class of languages decidable by time-T Turing machines with advice, denoted, contains every language L such that there exists a sequence of strings with and a TM M satisfying
for every, where on input the machine M runs for at most steps.

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 ⊆ P/poly then PH collapses to. This result is the Karp–Lipton theorem; furthermore, NP ⊆ P/poly implies AM = MA
If PSPACE ⊆ P/poly then, even PSPACE = MA.
If P^#P ⊆ P/poly then P^#P = MA. The proof is similar to above, based on an interactive protocol for permanent and #P-completeness of permanent.
If EXPTIME ⊆ P/poly then, even EXPTIME = MA.
If NEXPTIME ⊆ P/poly then NEXPTIME = EXPTIME, even NEXPTIME = MA. Conversely, NEXPTIME = MA implies NEXPTIME ⊆ P/poly
If EXP^NP ⊆ P/poly then
It is known that MA_EXP, an exponential version of MA, is not contained in P/poly.
The best known bound for the 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.

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.
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.

Bounded-error probabilistic polynomial is contained in P/poly

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; and this result was generalized to BPP ⊆ P/poly by Bennett and Gill.
Variants of the theorem show that BPL is contained in L/poly and AM is contained in NP/poly.

Proof

Let L be a language in BPP, and let M be a polynomial-time algorithm that decides L with error ≤ 1/3.
Construct a new machine ', which runs M 48n times and takes a majority vote of the results. Thus, ' is also polynomial-time, and has an error probability ≤ 1/eⁿ by the Chernoff bound. If we can fix R then we obtain an algorithm that is deterministic.
If is defined as, we have:
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
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.