Logarithmic space-constrained reduction

from Wikipedia, the free encyclopedia

A logarithmic space-constrained reduction (also called logarithmic reduction ) is a special form of reduction .

In addition to the requirement that a language can be reduced to another language by means of a function , it must also be possible to calculate this function in logarithmic space for a logarithmic reduction .

Logarithmic reductions are usually used in complexity theory to prove that a language of complexity class NL is also NL-complete .

The notation is often used here.

Note that transitivity can be shown for this reduction . This is the only way to work with this term.