Logarithmic space-constrained reduction

This article or the following section is not adequately provided with supporting documents ( e.g. individual evidence ). Information without sufficient evidence could be removed soon. Please help Wikipedia by researching the information and including good evidence.

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 . ${\displaystyle L'}$ ${\displaystyle L}$ ${\displaystyle f\;}$

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. ${\displaystyle A'\leq _{log}A}$

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