還元 (計算複雑性理論)

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

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

概要

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

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

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

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

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

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

定義

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

$\exists f\in F{\mbox{ . }}\forall x\in \mathbb {N} {\mbox{ . }}x\in A\Leftrightarrow f(x)\in B$

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

$A\leq _{F}B$

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

$\forall s\in S{\mbox{ . }}\forall A\in P(\mathbb {N} ){\mbox{ . }}A\leq s\Leftrightarrow A\in S$

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

$\forall s\in S{\mbox{ . }}s\leq A$

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

例

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

具体例

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

矛盾を導くため、E の判定器Rを想定する。これを使って（存在しないと分かっている）Hの判定器Sを作る。Mとw（チューリングマシンと入力文字列）を入力したときのS(M, w)の動作を以下のように定義する。S は、Mがwを入力したときに停止する場合だけ、wのみを受容するチューリングマシンNを生成するものとする（停止しない場合、空の言語を受容する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も決定不可能であることが導かれる。

注意

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

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

還元の種類と応用

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

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

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

関連項目

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

参考文献

• 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.