Loading article…
計算可能性理論と計算複雑性理論において、縮約とは、ある問題を別の問題に変換するアルゴリズムです。ある問題から別の問題への十分に効率的な縮約は、2 番目の問題が少なくとも最初の問題と同じくらい難しいことを示すために使用できます。
直感的には、問題A は問題Bに還元可能であるといえます。それは、問題B を効率的に解くアルゴリズム (存在する場合) が、問題A を効率的に解くためのサブルーチンとしても使用できる場合です。これが当てはまる場合、問題Aを解くことは問題B を解くことより困難ではあり得ません。「困難」とは、特定のコンテキストで必要な計算リソースの見積もりが高くなることを意味します (たとえば、時間の計算量が高い、メモリ要件が大きい、並列ソリューションではシングルスレッド ソリューションに比べて追加のハードウェア プロセッサ コアが必要になるなど)。A から B への還元の存在は、省略記法A ≤ m Bで表すことができます。通常、 ≤ には、使用されている還元の種類を示す下付き文字が付きます (m:マッピング還元、p:多項式還元)。
特定のタイプの簡約によって一連の問題に対して生成される数学的構造は、通常、前順序を形成し、その同値類は、解決不可能性の度合いと複雑性クラスを定義するために使用できます。
導入
削減を使用する必要がある主な状況は 2 つあります。
- まず、すでに解決した問題に似た問題を解決しようとしていることに気づきます。このような場合、新しい問題を素早く解決する方法は、新しい問題の各インスタンスを古い問題のインスタンスに変換し、既存のソリューションを使用してこれらを解決し、これらを使用して最終的なソリューションを取得することです。これはおそらく、リダクションの最も明白な使用法です。
- 2 番目: 解決が難しいことが証明されている問題があり、それに似た新しい問題があるとします。その問題も解決が難しいのではないかと疑うかもしれません。私たちは矛盾を主張します。つまり、新しい問題は簡単に解決できるとします。すると、古い問題のすべてのインスタンスを新しい問題のインスタンスに変換して解決することで簡単に解決できると示せれば、矛盾が生じます。これにより、新しい問題も難しいことが証明されます。
簡約の非常に簡単な例は、掛け算から二乗への変換です。私たちが知っているのは、加算、減算、二乗、2 で割ることだけだとします。この知識を次の公式と組み合わせて、任意の 2 つの数値の積を求めることができます。
逆方向の縮小もあります。明らかに、2 つの数を掛け算できる場合は、数を 2 乗できます。これは、これら 2 つの問題が同じくらい難しいことを意味しているようです。この種の縮小は、チューリング縮小に対応します。
しかし、二乗関数を 1 回だけ、しかも最後にしか使用できないという制限を加えると、簡約ははるかに難しくなります。この場合、乗算を含むすべての基本的な算術演算を使用できるとしても、一般に簡約は存在しません。なぜなら、平方として目的の結果を得るには、まずその平方根を計算する必要があり、この平方根は、有理数の算術演算では構成できないような無理数である可能性があるからです。ただし、逆の方向に進むと、最後に 1 回の乗算だけで数を二乗することは確かに可能です。この制限された形式の簡約を使用して、乗算は一般に二乗よりも難しいという意外ではない結果を示しました。これは、多対一の簡約に対応します。
プロパティ
リダクションとは、 P ( N )× P ( N )上の順序付け、つまり反射的かつ推移的な関係です。ここで、P ( N )は自然数のべき集合です。
削減の種類と用途
上記の例で説明したように、計算複雑性で使用される縮約には、多対一縮約とチューリング縮約の 2 つの主な種類があります。多対一縮約は、 1 つの問題のインスタンスを別の問題のインスタンスにマッピングします。チューリング縮約は、もう1 つの問題が簡単に解決できると仮定して、1 つの問題の解決策を計算します。多対一縮約は、より強力なタイプのチューリング縮約であり、問題を明確な複雑性クラスに分割するのに効果的です。ただし、多対一縮約に対する制限が増加すると、それらを見つけるのがより困難になります。
複雑性クラスのすべての問題がその問題に還元され、その問題がクラス自体にも含まれる場合、その問題は複雑性クラスにとって 完全です。この意味では、問題の任意の解は還元と組み合わせて、クラス内のすべての問題を解決するために使用できるため、問題はクラスを表します。
しかし、有用であるためには、縮約は容易でなければなりません。たとえば、ブール充足可能性問題のような解決困難なNP 完全問題を、指数時間で問題を解き、解がある場合のみ 0 を出力する縮約マシンにさせることで、数値が 0 に等しいかどうかの判定のような簡単な問題に縮約することは十分に可能です。しかし、これはあまり成果を上げません。なぜなら、新しい問題は解けるとしても、縮約を実行するのは古い問題を解決するのと同じくらい難しいからです。同様に、計算不可能な関数を計算する縮約は、決定不可能な問題を決定可能な問題に縮約することができます。Michael Sipser が「 Introduction to the Theory of Computation 」で指摘しているように、「縮約は、そのクラスの典型的な問題の複雑さに比べて容易でなければなりません [...] 縮約自体の計算が困難であれば、完全な問題に対する簡単な解が、それに縮約される問題に対する簡単な解を必ずしももたらすとは限りません。」
したがって、適切な縮約の概念は、研究対象の複雑性クラスによって異なります。複雑性クラスNPや、多項式階層などのより困難なクラスを研究する場合は、多項式時間の縮約が使用されます。 NCやNLなど、 P 内のクラスを研究する場合は、対数空間縮約が使用されます。縮約は、問題が機械によって解決可能かどうかを示すために計算可能性理論でも使用されます。この場合、縮約は計算可能関数のみに制限されます。
最適化（最大化または最小化）問題の場合、近似値を維持する削減という観点から考えることがよくあります。2 つの最適化問題があり、一方の問題のインスタンスをもう一方の問題のインスタンスにマッピングして、後者の問題のインスタンスのほぼ最適なソリューションを元のインスタンスに変換して、前者のほぼ最適なソリューションを生成できるとします。このように、問題 B のインスタンスに対してほぼ最適 (または最適) なソリューションを見つける最適化アルゴリズム(または近似アルゴリズム) と、問題 A から問題 B への効率的な近似保存縮小がある場合、それらを合成することで、問題 A のインスタンスに対してほぼ最適なソリューションを生み出す最適化アルゴリズムが得られます。近似保存縮小は、近似結果の困難性を証明するためによく使用されます。つまり、ある最適化問題 A が (何らかの複雑性の仮定の下で) ある α に対して α よりも良い係数内で近似することが困難であり、問題 A から問題 B への β 近似保存縮小がある場合、問題 B は係数 α/β 内で近似することが困難であると結論付けることができます。
例
- 決定問題P が決定不可能であることを示すには、決定不可能であることがすでにわかっている決定問題から P への簡約を見つける必要があります。その簡約関数は計算可能な関数でなければなりません。特に、停止問題がP に簡約されることを示すことによって、問題 P が決定不可能であることを示すことがよくあります。
- 複雑性クラスP、NP、PSPACE は、（多対一、「Karp」）多項式時間削減の下で閉じています。
- 複雑性クラスL、NL、P、NP、PSPACEは、対数空間削減に対して閉じています。
詳細な例
次の例は、停止問題からの還元を使用して言語が決定不能であることを証明する方法を示しています。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も決定不可能であることがわかります。
参照
参考文献
- Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein、『アルゴリズム入門』、MIT Press、2001 年、ISBN 978-0-262-03293-3
- Hartley Rogers, Jr.: 再帰関数と効果的な計算可能性の理論、McGraw-Hill、1967年、ISBN 978-0-262-68052-3。
- Peter Bürgisser: 代数的複雑性理論における完全性と簡約、Springer、2000年、ISBN 978-3-540-66752-0。
- ER Griffor: 計算可能性理論ハンドブック、North Holland、1999年、ISBN 978-0-444-89882-1。