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 of languages that have a polynomial-size non-uniform circuit family, non-uniform PSIZE. 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 ... more

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 of languages that have a polynomial-size non-uniform circuit family, non-uniform PSIZE. 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, if we're testing a 32-bit number, it is enough to test a = 2, 7, and 61. This follows from the fact that for each composite n, 3/4s of all possible a... less