還元の種類と応用

ウィキペディア小見出し辞書

還元の種類と応用

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/20 05:47 UTC 版)

「還元 (計算複雑性理論)」の記事における「還元の種類と応用」の解説

上述の例にあるように、計算複雑性理論で使われる還元にはチューリング還元と多対一還元の2種類がある。多対一還元はある問題の複数のインスタンスを別の問題の複数のインスタンスにマッピングする。チューリング還元はある問題を解くのが簡単であると仮定して、もうひとつの問題の解法を「計算」する。多対一還元はチューリング還元よりも弱い。弱い還元のほうが問題を区別する際には効果的だが、還元を設計する能力が弱いのである。 しかし、実用的観点からは還元は簡単でなければならない。例えば、解くのが難しい充足可能性問題のようなNP完全問題を、ある数が零かどうかを判定するような瑣末な問題に還元することも可能である。これは例えば、指数時間をかけて問題を解き、解があるときに零を出力するような還元機械を想定すればよい。しかし、これはあまり意味がない。というのも、このような複雑な還元を考えるのと、新たな問題の解法を考えるのとでは労力があまり変わらないからである。 従って、還元を議論する際にはある特定の複雑性クラスに関する議論であると見なすのが一般的である。NPやそれより困難な複雑性クラスの研究においては多項式時間多対一還元が使われる。多項式階層で複雑性クラスを定義する場合、多項式時間チューリング還元が使われる。P に含まれる複雑性クラス（NC、NL）では対数空間還元が使われる。還元は計算可能性理論でも使われ、ある問題を機械で計算可能かどうかの判定に使われる。この場合の還元は計算可能関数に限定される。