L/poly

From Wikipedia, the free encyclopedia

This article is orphaned as few or no other articles link to it. Please help introduce links in articles on related topics. (November 2006)

L/poly is the complexity class of logarithmic space machines with a polynomial amount of advice. It is defined similarly to the more-well-known class P/poly.

It can be shown that L/poly is equivalent to uniform polyBP, the class of uniform polynomial-sized branching programs.