More precisely, it is the set of formal languages that have polynomial-size circuit families.
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.
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
[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
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.
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.
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
can be defined using Turing machines that "take advice".
, which it is allowed to use in its computation whenever the input has size n. To help visualize this equivalence, imagine the advice for each n is a description of a boolean circuit having n inputs, and the Turing Machine evaluating that boolean circuit on inputs of length n. Let
The class of languages decidable by time-T(n) Turing machines with
For theoretical computer science, there are several important properties that depend on 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, NPA is not a subset of PA/poly with probability 1.
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.
[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.
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/en by the Chernoff bound (see BPP).