If such a reduction exists, then every algorithm for M immediately yields an algorithm for L, with only a modest (i.e. polynomial) slowdown.
The intuitive notion of reducibility can be formalized in different ways: see polynomialtime manyone reduction and logarithmicspace manyone reduction[?].
Search Encyclopedia

Featured Article
