還元 (計算複雑性理論)

還元（かんげん、Reduction）について

還元とは、計算可能性理論や計算複雑性理論において、ある問題を別の問題に変換することを指します。このプロセスは、ある問題の解決を他の問題の解決に依存させるものであり、しばしば「帰着」「変換」とも呼ばれます。問題の複雑性を理解するためには、この還元の方法が重要で、変換がどのように行われるかによって問題の複雑性クラスを定義することができます。

還元の基本的な考え方

ある問題Aが他の問題Bに還元されるということは、Bを解くことでAの解を得ることができることを意味します。つまり、Aを解くことはBを解くことよりも難しくないという関係が成り立ちます。この関係は、A ≤ Bと表記され、≤に添え字を付けることで還元の種類を示すことができます。

例えば、過去に解いた問題に似た新しい問題が現れた場合、迅速に解決するためには、その新しい問題を既知の問題に還元し、既存の解法を用いることが有効です。新しい問題を過去の問題に変換し、得た解を逆変換することで最終的な解答を得るという方法が還元の一般的なアプローチです。

還元の種類と例

還元には複数の種類がありますが、最も基本的な例は「乗算」と「平方への還元」です。加算、減算、平方、および数での除算などの知識だけを用いて、次の方程式を介して任意の二つの数の積を得ることができます:

```
a × b = ((a + b)² - a² - b²)/2
```

ここでは、乗算を知っていれば平方を求めることも容易です。したがって、これら二つの問題は同じ複雑性を持つことが示されています。

さらに、ある問題が解決困難であることがわかっている時、それに似た新しい問題も困難であると仮定することができます。この場合、新しい問題が簡単に解けると仮定すると矛盾が生じます。これは、問題の相対的な困難性を評価する手段ともなります。

還元の定義と特性

数学的に、自然数Nの部分集合AとBがあり、NからNへの関数の集合Fがある時、AはBに還元可能であると言えます。具体的には、次のように定義されます:

```
∃ f ∈ F . ∀ x ∈ N . x ∈ A ⇔ f(x) ∈ B
```

この関係はA ≤F Bという形で記述されます。また、ある複雑性クラスにおいてすべての問題が特定の問題に還元される場合、その問題はそのクラス内で完全とされます。

還元の応用例

具体的には、ある決定問題が決定不可能であることを示す際には、計算可能関数を用いて既知の決定不可能問題に還元する手法がよく使われます。たとえば、チューリングマシンの停止問題は、他の決定問題が決定不可能であることを示す一例として頻繁に用いられます。複雑性クラスPなどは、多項式時間還元において閉じています。

還元の重要性

還元は計算可能性や計算複雑性を理解する鍵となる概念です。この概念を通じて、問題間の関係や相対的な難易度を判断することが可能となります。そして、我々は特定の問題の解決を別の問題の解決に依存させることで、新たな解法を探求する道が開かれるのです。

参考文献

• - Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2001). Introduction to Algorithms. MIT Press.
• - Rogers, H. (1967). Theory of Recursive Functions and Effective Computability. McGraw-Hill.
• - Bürgisser, P. (2000). Completeness and Reduction in Algebraic Complexity Theory. Springer.
• - Griffor, E. R. (1999). Handbook of Computability Theory. North Holland.

もう一度検索