還元 (計算複雑性理論)

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

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

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

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

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

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

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

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

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

${\displaystyle A\leq _{F}B}$

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

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

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

${\displaystyle \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)という反射的関係であると同時に推移的関係でもある。

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