Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/L/poly> ?p ?o }
Showing triples 1 to 34 of
34
with 100 triples per page.
- poly abstract "In computational complexity theory, L/poly is the complexity class of logarithmic space machines with a polynomial amount of advice. L/poly is a non-uniform logarithmic space class, analogous to the non-uniform polynomial time class P/poly.Formally, for a formal language L to belong to L/poly, there must exist an advice function f that maps an integer n to a string of length polynomial in n, and a Turing machine M with two read-only input tapes and one read-write tape of size logarithmic in the input size, such that an input x of length n belongs to L if and only if machine M accepts the input x, f(n). Alternatively and more simply, L is in L/poly if and only if it can be recognized by branching programs of polynomial size. One direction of the proof that these two models of computation are equivalent in power is the observation that, if a branching program of polynomial size exists, it can be specified by the advice function and simulated by the Turing machine. In the other direction, a Turing machine with logarithmic writable space and a polynomial advice tape may be simulated by a branching program the states of which represent the combination of the configuration of the writable tape and the position of the Turing machine heads on the other two tapes.In 1979, Aleliunas et al. showed that symmetric logspace is contained in L/poly. However, this result was superseded by Omer Reingold's result that SL collapses to uniform logspace.BPL is contained in L/poly, which is a variant of Adleman's theorem.".
- poly wikiPageID "7192559".
- poly wikiPageLength "3912".
- poly wikiPageOutDegree "14".
- poly wikiPageRevisionID "535473797".
- poly wikiPageWikiLink Advice_(complexity).
- poly wikiPageWikiLink BPL_(complexity).
- poly wikiPageWikiLink Binary_decision_diagram.
- poly wikiPageWikiLink Category:Complexity_classes.
- poly wikiPageWikiLink Circuit_complexity.
- poly wikiPageWikiLink Complexity_class.
- poly wikiPageWikiLink Computational_complexity_theory.
- poly wikiPageWikiLink Formal_language.
- poly wikiPageWikiLink L_(complexity).
- poly wikiPageWikiLink Omer_Reingold.
- poly wikiPageWikiLink poly.
- poly wikiPageWikiLink SL_(complexity).
- poly wikiPageWikiLink Turing_machine.
- poly wikiPageWikiLinkText "L/poly".
- poly wikiPageUsesTemplate Template:Comp-sci-theory-stub.
- poly wikiPageUsesTemplate Template:Math.
- poly wikiPageUsesTemplate Template:Mvar.
- poly wikiPageUsesTemplate Template:Reflist.
- poly subject Category:Complexity_classes.
- poly hypernym Class.
- poly type Class.
- poly comment "In computational complexity theory, L/poly is the complexity class of logarithmic space machines with a polynomial amount of advice.".
- poly label "L/poly".
- poly sameAs Q6456811.
- poly sameAs Poly.
- poly sameAs m.025vpm1.
- poly sameAs Q6456811.
- poly wasDerivedFrom poly?oldid=535473797.
- poly isPrimaryTopicOf poly.