対数領域還元
対数領域還元(たいすうりょういきかんげん、英: Log-space reduction)は、計算複雑性理論において、決定性チューリング機械で対数領域を使って計算可能な還元である。概念的には、入力を一定数のポインタで指すことで、固定の対数領域だけを使用する。そのような機械の構成は多項式的に多数存在するので、対数領域還元は多項式時間還元でもある。
対数領域還元は多項式時間還元よりも弱いと考えられ、P に属する空でなく全体でもない言語は、P に属する別の空でなく全体でない言語に多項式時間還元可能だが、NL に属する言語とL に属する言語(共に P に包含される)との間の対数領域還元は L = NL ではないことを暗に示している。NP完全問題が、対数領域還元と多項式時間還元において異なるかどうかは未解決の問題である。
対数領域還元は P に属する言語について使われることが多く、それが多対一還元なのかチューリング還元なのかは問題とされないことが多い。