Matches in DBpedia 2014 for { <http://dbpedia.org/resource/P/poly> ?p ?o. }
Showing items 1 to 22 of
22
with 100 items per page.
- poly abstract "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 PSIZE of languages that have a polynomial-size circuits. 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 values are witnesses; a simple counting argument similar to the one in the proof that BPP in P/poly below shows that there exists a suitable list of a values for every input size, although finding it may be expensive.Note that 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 example above.".
- poly wikiPageID "2052415".
- poly wikiPageRevisionID "603845176".
- poly hasPhotoCollection poly.
- poly subject Category:Complexity_classes.
- poly type Abstraction100002137.
- poly type Class107997703.
- poly type Collection107951464.
- poly type ComplexityClasses.
- poly type Group100031264.
- poly comment "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 PSIZE of languages that have a polynomial-size circuits.".
- poly label "P/polinomial".
- poly label "P/poly".
- poly label "P/poly".
- poly sameAs poly.
- poly sameAs polinomial.
- poly sameAs m.06hrjg.
- poly sameAs Q7117817.
- poly sameAs Q7117817.
- poly sameAs poly.
- poly wasDerivedFrom poly?oldid=603845176.
- poly isPrimaryTopicOf poly.