✳flâneur — a map of the web's best reading

P/poly - Wikipedia

en.wikipedia.org · 2,250 words · saved by 1 readers

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.[1][2] 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

P/poly - Wikipedia Jump to content From Wikipedia, the free encyclopedia Set of problems solved by small circuits 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 defi

Explore this link on the map →

related reading