L/poly
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. 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.
Link from a Wikipage to another Wikipage
primaryTopic
L/poly
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. 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.
has abstract
In computational complexity th ...... variant of Adleman's theorem.
@en
Wikipage page ID
page length (characters) of wiki page
Wikipage revision ID
746,934,780
Link from a Wikipage to another Wikipage
wikiPageUsesTemplate
subject
hypernym
comment
In computational complexity th ...... variant of Adleman's theorem.
@en
label
L/Poly
@pt
L/poly
@en