還元 (計算複雑性理論)

還元とは、計算可能性理論や計算複雑性理論において、ある問題を別の問題に変換することを意味する。帰着、変換などとも呼ばれる。変換の仕方によっては、問題の複雑性クラスを定義するのに使われる。

直観的に、問題 A が問題 B に還元されるとき、B の解法によって A の答えも得られる。従って A を解くことは B を解くよりも困難ではない。これを A ≤ B のように表記し、≤ に添え字をつけて還元の種類を示す。

1. 概要
-----

過去に解いたことのある問題によく似た問題に出会うことは珍しくない。そのような場合、その新しい問題を素早く解くには、新しい問題を過去の問題に変換して既知の解法で解くのがよいだろう。そして、逆変換することで最終的な答えが得られる。これは還元の最も分かり易い例である。

また、やや複雑な使用法だが、解くのが難しいことが分かっている問題があり、それとよく似た問題を与えられたとする。その新たな問題も同様に難しいのではないかと考えることだろう。ここで逆説的にその新しい問題は簡単に解けると仮定する。その上で過去の問題を新たな問題に簡単に変換することができたとすると矛盾が生じる。つまり、新たな問題も難しいということが分かるのである。

還元の非常に簡単な例を示す。それは「乗算」から「平方」への還元である。我々が加算、減算、平方、2での除算しか知らないとする。その知識だけから、以下の方程式を使うと、任意の2つの数の積を得ることができる:

//a// × //b// = 2 - a2 - b2)/2.逆方向の還元も可能である。乗算を知っているなら平方を計算するのはたやすい。つまり、この2つの問題の複雑性は等しいことがわかる。このような還元はチューリング還元に関係する。

しかし、例えば平方は最後に1回しかできないといった制限を加えられると還元が難しくなる。この場合たとえ乗算を含めた基本的演算を全て使用できたとしても還元は不可能である。というのも有理数からのような無理数を求めることはできないからである。逆方向では、最後に必ず乗算を行うという制限があっても全く問題なく平方を求めることができる。このような制限された還元を考えることで、乗算のほうが平方よりも複雑であるという事実が明らかとなる。これは多対一還元に関係する。

2. 定義
-----

自然数Nの部分集合 //A// と //B// があり、NからNへの関数の集合 //F// があるとき、次の場合に //F// において //A// が //B// に還元可能である。

これを次のように記述する。

P の部分集合 //S// があり、還元を ≤ で表すと、次の場合に ≤ において //S// が閉じている。

Nの部分集合 //A// は、次の場合に //S//に対して困難である。

//A//が//S//に対して困難で、かつ//A//が//S//に含まれる場合に、Nの部分集合//A//は //S// に対して完全である。

3. 例
----

ある決定問題が決定不可能であることを示すために、計算可能関数を使ってそれを既に決定不可能と分かっている決定問題に変換する。特に、ある問題が決定不能であることを示すために、チューリングマシンの停止問題がその問題に還元可能であることを示すという手法がよく使われる。
複雑性クラス P、NP、PSPACE は多項式時間還元において閉じている。
複雑性クラス L、NL、P、NP、PSPACE は対数空間還元において閉じている。

3.1. 具体例
--------

ある言語が決定不可能であることを停止問題からの還元で示す例を以下で示す。チューリングマシン //M// が入力文字列//w//について停止するかどうかという問題を //H// と表記する。この言語は決定不可能であることが知られている。チューリングマシン//M//の受容する文字列がないかどうかという決定問題を //E// と表記する。//E// が決定不可能であることを //H// からの還元によって示す。

矛盾を導くため、//E// の判定器//R//を想定する。これを使って//H//の判定器//S//を作る。//M//と//w//を入力したときの//S//の動作を以下のように定義する。//S// は、//M//が//w//を入力したときに停止する場合だけ、//w//のみを受容するチューリングマシン//N//を生成するものとする。すると、判定器 //S// は //R// を評価して//N//の受容する言語が空であるかどうかを判定できる。//R//が//N//を受容するなら、//N//の受容する言語は空であり、//M//が入力//w//で停止しないから、//S//はそのように判定できる。//R//が//N//を受容しないなら//N//の受容する言語は空ではなく、//M//は入力//w//で停止するので、//S//はそのように判定する。従って、//E//の判定器//R//があれば、任意のマシン//M//と入力//w//に関する停止問題//H//の判定器//S//を作ることができる。そのような//S//は存在しないことが既知であるため、言語//E//も決定不可能であることが導かれる。

4. 注意
-----

還元は前順序的であり、自然数の冪集合 Pに関して P×Pという反射的関係であると同時に推移的関係でもある。

ある複雑性クラスの問題が全て特定の問題に還元されるなら、その問題をその複雑性において完全であるといい、クラスそのものを表す。この意味でクラスを表す問題は、還元と組み合わせてそのクラスのあらゆる問題を解くのに使われる。

5. 還元の種類と応用
-----------

上述の例にあるように、計算複雑性理論で使われる還元にはチューリング還元と多対一還元の2種類がある。多対一還元はある問題の複数のインスタンスを別の問題の複数のインスタンスにマッピングする。チューリング還元はある問題を解くのが簡単であると仮定して、もうひとつの問題の解法を「計算」する。多対一還元はチューリング還元よりも弱い。弱い還元のほうが問題を区別する際には効果的だが、還元を設計する能力が弱いのである。

しかし、実用的観点からは還元は簡単でなければならない。例えば、解くのが難しい充足可能性問題のようなNP完全問題を、ある数が零かどうかを判定するような瑣末な問題に還元することも可能である。これは例えば、指数時間をかけて問題を解き、解があるときに零を出力するような還元機械を想定すればよい。しかし、これはあまり意味がない。というのも、このような複雑な還元を考えるのと、新たな問題の解法を考えるのとでは労力があまり変わらないからである。

従って、還元を議論する際にはある特定の複雑性クラスに関する議論であると見なすのが一般的である。NPやそれより困難な複雑性クラスの研究においては多項式時間多対一還元が使われる。多項式階層で複雑性クラスを定義する場合、多項式時間チューリング還元が使われる。P に含まれる複雑性クラスでは対数空間還元が使われる。還元は計算可能性理論でも使われ、ある問題を機械で計算可能かどうかの判定に使われる。この場合の還元は計算可能関数に限定される。

6. 関連項目
-------

多対一還元
真理値表還元
チューリング還元
最適化

7. 参考文献
-------

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, MIT Press, 2001, ISBN 978-0-262-03293-3
Hartley Rogers, Jr.: Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967, ISBN 978-0262680523.
Peter Bürgisser: Completeness and Reduction in Algebraic Complexity Theory, Springer, 2000, ISBN 978-3540667520.
E.R. Griffor: Handbook of Computability Theory, North Holland, 1999, ISBN 978-0444898821.