L/poly: Difference between revisions
Content deleted Content added
m Date/fix the maintenance tags using AWB |
m Date/fix the maintenance tags or gen fixes |
||
| Line 1: | Line 1: | ||
{{Orphan|November 2006}} |
{{Orphan|date=November 2006}} |
||
'''L/poly''' is the [[complexity class]] of [[logarithmic space]] machines with a polynomial amount of [[advice (complexity)|advice]]. It is defined similarly to the more-well-known class [[P/poly]]. |
'''L/poly''' is the [[complexity class]] of [[logarithmic space]] machines with a polynomial amount of [[advice (complexity)|advice]]. It is defined similarly to the more-well-known class [[P/poly]]. |
||
Revision as of 16:35, 28 April 2007
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.
 | This computer science article is a stub. You can help Wikipedia by expanding it. |