Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/P/poly> ?p ?o }
Showing triples 1 to 65 of
65
with 100 triples 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 wikiPageLength "10322".
- poly wikiPageOutDegree "37".
- poly wikiPageRevisionID "682199198".
- poly wikiPageWikiLink Advice_(complexity).
- poly wikiPageWikiLink Arthur-Merlin_protocol.
- poly wikiPageWikiLink Arthur–Merlin_protocol.
- poly wikiPageWikiLink BPL_(complexity).
- poly wikiPageWikiLink BPP_(complexity).
- poly wikiPageWikiLink Binary_decision_diagram.
- poly wikiPageWikiLink Bounded-error_probabilistic_polynomial.
- poly wikiPageWikiLink Branching_program.
- poly wikiPageWikiLink Category:Complexity_classes.
- poly wikiPageWikiLink Charles_H._Bennett_(computer_scientist).
- poly wikiPageWikiLink Complexity_class.
- poly wikiPageWikiLink Computational_complexity_theory.
- poly wikiPageWikiLink Cryptography.
- poly wikiPageWikiLink EXPTIME.
- poly wikiPageWikiLink Formal_language.
- poly wikiPageWikiLink IP_(complexity).
- poly wikiPageWikiLink Karp–Lipton_theorem.
- poly wikiPageWikiLink poly.
- poly wikiPageWikiLink L_(complexity).
- poly wikiPageWikiLink Leonard_Adleman.
- poly wikiPageWikiLink Logarithmic_space.
- poly wikiPageWikiLink Miller–Rabin_primality_test.
- poly wikiPageWikiLink NEXPTIME.
- poly wikiPageWikiLink NP_(complexity).
- poly wikiPageWikiLink PSPACE.
- poly wikiPageWikiLink P_(complexity).
- poly wikiPageWikiLink Padding_argument.
- poly wikiPageWikiLink Permanent_is_sharp-P-complete.
- poly wikiPageWikiLink Polynomial-time_Turing_reduction.
- poly wikiPageWikiLink Polynomial-time_reduction.
- poly wikiPageWikiLink Polynomial_hierarchy.
- poly wikiPageWikiLink RP_(complexity).
- poly wikiPageWikiLink Rainbow_table.
- poly wikiPageWikiLink Sharp-P.
- poly wikiPageWikiLink Sharp-P-completeness_of_01-permanent.
- poly wikiPageWikiLink Sharp_P.
- poly wikiPageWikiLink Sparse_language.
- poly wikiPageWikiLink Turing_machine.
- poly wikiPageWikiLink Unary_language.
- poly wikiPageWikiLink Undecidable_problem.
- poly wikiPageWikiLinkText "'''P'''/poly".
- poly wikiPageWikiLinkText "Adleman's theorem".
- poly wikiPageWikiLinkText "P/poly".
- poly wikiPageWikiLinkText "polynomial size circuits".
- poly hasPhotoCollection poly.
- poly wikiPageUsesTemplate Template:.
- poly wikiPageUsesTemplate Template:ComplexityClasses.
- poly wikiPageUsesTemplate Template:Reflist.
- poly subject Category:Complexity_classes.
- poly hypernym Class.
- poly type Class.
- 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/poly".
- poly sameAs poly.
- poly sameAs polinomial.
- poly sameAs m.06hrjg.
- poly sameAs Q7117817.
- poly sameAs Q7117817.
- poly wasDerivedFrom poly?oldid=682199198.
- poly isPrimaryTopicOf poly.