Log-space reduction

A logarithmic space limited reduction ( also referred to as a log reduction ) is a special form of the reduction.

In addition to the requirement that a language to another language can be reduced by means of a function, this function must be calculated on a logarithmic space for a log reduction in addition.

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

Notation is used herein as a common.

Note that for this reduction transitivity can be shown. Only then can you work with this concept.

• Complexity Theory