チューリング還元
しかしながら、多項式時間還元はクラス P の中で用いるには不適当である。何故なら P に属する如何なる問題も、P に属する他の殆ど全ての問題に（多対一還元でもチューリング還元でも）多項式時間帰着できるからである。従って、P の中に存在するクラス（例えばNL、NC や P 自身）については、代わりに対数領域還元が用いられる。