対数領域還元
(対数空間還元 から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/20 07:06 UTC 版)
対数領域還元（たいすうりょういきかんげん、英: Log-space reduction）は、計算複雑性理論において、決定性チューリング機械で対数領域を使って計算可能な還元である。概念的には、入力を一定数のポインタで指すことで、固定の対数領域だけを使用する。そのような機械の構成は多項式的に多数存在するので、対数領域還元は多項式時間還元でもある。
- ^ ここで「ほとんど」としたのは、他の問題を多対一還元することができない（チューリング還元は可能）問題（その補問題）が少なくとも1つ存在するためである。その問題とは、全ての入力を受容する問題（補問題は全ての入力を拒否する）である。
[続きの解説]
「対数領域還元」の続きの解説一覧
- 1 対数領域還元とは
- 2 対数領域還元の概要
- 対数領域還元のページへのリンク
