Logarithmic space-constrained reduction
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.