対数領域還元
なぜなら、L、SL、NL、P はチューリング還元において閉じており、チューリング還元を施すことで問題がそれらのクラスに属することを示すことが可能であるからである。しかし、NC も P に包含されるが、チューリング還元において閉じていないため、多対一還元を使わなければならない。
多項式時間還元が P やそのサブクラスではあまり意味がないのと同様、対数領域還元も L とそのサブクラスを区別するのには役立たない。L に属するほとんどの問題は、対数領域還元の下でL完全である。より弱い還元があったとしても、単に問題を L の真部分集合である言語に先延ばしするだけであるため、実際には使われることはほとんどない。
対数領域還元のためのツールは、L = SL という結果によって大きく拡張されてきた。SL完全問題は、今では対数領域還元のサブルーチンとして利用されている。