対数領域還元
(対数領域帰着 から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/20 07:06 UTC 版)
ナビゲーションに移動 検索に移動 | この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（2016年9月） |
対数領域還元（たいすうりょういきかんげん、英: Log-space reduction）は、計算複雑性理論において、決定性チューリング機械で対数領域を使って計算可能な還元である。概念的には、入力を一定数のポインタで指すことで、固定の対数領域だけを使用する。そのような機械の構成は多項式的に多数存在するので、対数領域還元は多項式時間還元でもある。
対数領域還元は多項式時間還元よりも弱いと考えられ、P に属する空でなく全体でもない言語は、P に属する別の空でなく全体でない言語に多項式時間還元可能だが、NL に属する言語とL に属する言語（共に P に包含される）との間の対数領域還元は L = NL ではないことを暗に示している。NP完全問題が、対数領域還元と多項式時間還元において異なるかどうかは未解決の問題である。
対数領域還元は P に属する言語について使われることが多く、それが多対一還元なのかチューリング還元なのかは問題とされないことが多い。なぜなら、L、SL、NL、P はチューリング還元において閉じており、チューリング還元を施すことで問題がそれらのクラスに属することを示すことが可能であるからである。しかし、NC も P に包含されるが、チューリング還元において閉じていないため、多対一還元を使わなければならない。
多項式時間還元が P やそのサブクラスではあまり意味がないのと同様、対数領域還元も L とそのサブクラスを区別するのには役立たない。L に属するほとんどの問題[1]は、対数領域還元の下でL完全である。より弱い還元があったとしても、単に問題を L の真部分集合である言語に先延ばしするだけであるため、実際には使われることはほとんどない。
対数領域還元のためのツールは、L = SL という結果によって大きく拡張されてきた。SL完全問題は、今では対数領域還元のサブルーチンとして利用されている。
脚注
- ^ ここで「ほとんど」としたのは、他の問題を多対一還元することができない（チューリング還元は可能）問題（その補問題）が少なくとも1つ存在するためである。その問題とは、全ての入力を受容する問題（補問題は全ての入力を拒否する）である。
- 対数領域還元のページへのリンク
