Loading article…
計算可能性理論および計算複雑性理論において、還元とは、ある問題を別の問題に変換するアルゴリズムのことである。ある問題から別の問題への十分効率的な還元を用いることで、後者の問題が前者の問題と少なくとも同程度に難しいことを示すことができる。
直感的に言えば、問題Aは問題Bに還元可能である。これは、問題B を効率的に解くアルゴリズム (存在する場合) が、問題A を効率的に解くためのサブルーチンとしても使用できる場合である。これが真である場合、 A を解くことはBを解くことよりも難しくはない。「難しい」とは、特定の状況で必要な計算リソースの見積もりが高いことを意味する (例えば、時間計算量が高い、メモリ要件が大きい、並列解法ではシングルスレッド解法に比べて追加のハードウェアプロセッサコアが必要など)。A からBへの還元が存在することは、通常、≤ に添え字を付けて使用されている還元の種類を示す略記法A ≤ m Bで表すことができる(m :多対一還元、p :多項式還元)。
特定のタイプの還元によって一連の問題上に生成される数学的構造は、一般に前順序を形成し、その同値類は、解決不可能性の度合いや複雑性クラスを定義するために使用できます。
縮約を用いる必要がある主な状況は2つあります。
簡略化の非常に簡単な例として、乗算から平方への変換が挙げられます。私たちが知っている操作は、足し算、引き算、平方、2で割ることだけだとしましょう。この知識と次の公式を組み合わせることで、任意の2つの数の積を求めることができます。
逆方向の還元も存在します。明らかに、2つの数を掛け合わせることができるなら、1つの数を2乗することもできます。これは、これら2つの問題が同じくらい難しいことを示唆しているようです。この種の還元はチューリング還元に相当します。
しかし、二乗関数を一度だけ、しかも最後にしか使用できないという制約を加えると、還元ははるかに難しくなります。この場合、乗算を含むすべての基本的な算術演算の使用が許可されていても、一般的に還元は存在しません。なぜなら、目的の結果を二乗として得るには、まずその平方根を計算する必要があり、この平方根は次のような無理数になる可能性があるからです。これは、有理数に対する算術演算では構成できないものです。しかし、反対方向に考えると、最後に1回の乗算を行うだけで、確かに数を2乗することができます。この限定的な形式の還元を用いることで、乗算は一般的に2乗よりも難しいという、驚くべきことではない結果を示しました。これは多対一還元に対応します。
還元可能性は、P ( N ) × P ( N )上の前順序、つまり反射的かつ推移的な関係です。ここで、 P ( N ) は自然数の冪集合です。
上記の例で説明したように、計算複雑性理論では、主に2種類の還元法、すなわち多対一還元とチューリング還元が用いられます。多対一還元は、ある問題のインスタンスを別の問題のインスタンスにマッピングするものであり、チューリング還元は、一方の問題の解を計算し、もう一方の問題は容易に解けると仮定するものです。多対一還元はチューリング還元のより強力な形態であり、問題を明確な複雑性クラスに分類するのに効果的です。しかし、多対一還元には制約が多いため、見つけるのがより困難になります。
ある複雑性クラスにおいて、問題が完全であるとは、そのクラス内のすべての問題がその問題に還元され、かつその問題自体がそのクラスに含まれている場合をいう。この意味で、その問題はクラスを代表するものである。なぜなら、その問題の解は、還元と組み合わせることで、クラス内のすべての問題を解決するために使用できるからである。
しかし、有用であるためには、還元は容易でなければなりません。例えば、ブール充足可能性問題のような解決困難なNP完全問題を、還元マシンに指数時間で問題を解かせ、解が存在する場合にのみゼロを出力するようにすれば、ある数がゼロに等しいかどうかを判定するような自明な問題に還元することは十分に可能です。しかし、これによって得られる成果はそれほど大きくありません。なぜなら、新しい問題を解くことはできても、還元を実行すること自体は、元の問題を解くのと同じくらい難しいからです。同様に、計算不可能な関数を計算する還元は、決定不能な問題を決定可能な問題に還元することができます。マイケル・シプサーが『計算理論入門』で指摘しているように、「還元は、そのクラスの典型的な問題の複雑さに比べて容易でなければならない。[...] 還元自体が計算困難であれば、完全な問題に対する容易な解が、それに還元される問題に対する容易な解を必ずしももたらすとは限らない。」
したがって、適切な還元概念は、研究対象の複雑性クラスによって異なります。複雑性クラスNPや多項式階層などのより困難なクラスを研究する場合、多項式時間還元が使用されます。P内のNCやNLなどのクラスを研究する場合、対数空間還元が使用されます。還元は、計算可能性理論において、問題が機械で解決可能かどうかを示すためにも使用されます。この場合、還元は計算可能な関数（多対一還元の場合）またはオラクルマシン（チューリング還元の場合）のみに限定されます。
最適化問題（最大化または最小化）の場合、近似保存還元という観点から考えることがよくあります。2 つの最適化問題があり、一方の問題のインスタンスを他方の問題のインスタンスにマッピングできるとします。後者の問題のインスタンスに対するほぼ最適な解を前者のほぼ最適な解に変換し直すことができます。このように、問題Bのインスタンスに対してほぼ最適な（または最適な）解を見つける最適化アルゴリズム（または近似アルゴリズム）と、問題Aから問題Bへの効率的な近似保存還元があれば、合成によって問題Aのインスタンスに対してほぼ最適な解を与える最適化アルゴリズムが得られます。近似保存還元は、近似結果の困難性を証明するためによく使用されます。ある最適化問題A が(ある複雑性仮定の下で) あるαに対してαよりも優れた係数で近似するのが困難であり、問題Aから問題Bへのβ近似保存還元が存在する場合、問題Bは係数α / βで近似するのが困難であると結論付けることができます。
次の例は、停止問題からの還元を使用して言語が決定不能であることを証明する方法を示しています。H ( M , w )は、与えられたチューリングマシンM が入力文字列wに対して停止するかどうか (受理または拒否によって)を判定する問題であるとします。この言語は決定不能であることが知られています。E ( M )は、与えられたチューリングマシンMが受理する言語が空であるかどうか (つまり、M が文字列を一切受理するかどうか)を判定する問題であるとします。Hからの還元によって、Eが決定不能であることを示します。
矛盾を得るために、R がEの判定器であると仮定します。これを使用して、 Hの判定器Sを生成します(これは存在しないことがわかっています)。入力Mとw (チューリング マシンと何らかの入力文字列) が与えられたとき、次の動作でS ( M , w ) を定義します。Sは、 Nへの入力文字列がwであり、M が入力wで停止する場合にのみ受理し、それ以外の場合は停止しないチューリング マシンNを生成します。判定器Sは、 R ( N )を評価して、N が受理する言語が空かどうかを確認できます。RがNを受理する場合、Nが受理する言語は空であるため、特にM は入力wで停止しないため、S は拒否できます。R が N を拒否する場合、Nが受理する言語は空ではないため、M は入力wで停止するため、S は受理できます。したがって、 Eの判定器Rがあれば、任意のマシンMと入力wに対して、停止問題H ( M , w )の判定器Sを生成できます。そのようなSが存在し得ないことがわかっているので、言語Eも決定不能であるという結論が導かれる。
