多対一還元とチューリング還元

はじめに

計算理論における「還元（reduction）」という用語は、私の過去の記事でも多用されています。
ざっくり言うと、ある問題を別の問題に変換することを指すのですが、これまで私は「還元」について深く説明することがありませんでした。

というのも、実は還元にも「強さ」があり、一つの記事内で説明するにはボリュームがありすぎるからです。

この記事では、多対一還元、チューリング還元について説明し、厳密な意味での「還元」を理解することを目指します。

神託と神託機械

神託

計算理論における神託（oracle）とは、ある決定問題の答え（YES/NO）を1ステップで得ることができるツール（ブラックボックスと説明されることが多い）です。

しばしば問題自体を神託としてとらえ、問題と同じ文字で神託を表現することがあります。

ある決定問題の答えを与える神託が、別の決定問題の答えを与える能力を持つとは限りません。神託は唯一の存在ではなく、特定の問題の答えを爆速で返す関数みたいなもんです。
一応、すべての入力に対する出力を記憶しておけば神託は実現できないこともない（できないかも）ですが、まあ現実には存在しないと考えてよいでしょう¹。

神託機械

神託機械（oracle machine）とは、神託が付属したチューリングマシンのことです。

チューリングマシンなんて使うまでもなく、神託だけで問題を解けばいいじゃんと思われるかもしれませんが、このような抽象機械を考える理由が、まさに「還元」です。

仮に問題$A$を解く神託（問題$A$をオラクルとして用いる）があるとしましょう。
このとき、問題$B$を愚直に解くよりも、問題Aの答えを用いることで効率的に解ける場合があります。

例えば、グラフ$G=(V, E)$に対するハミルトン閉路問題²を解く場合、これはNP完全問題であることが知られていて³、「今のところ」は多項式時間でこれを解くアルゴリズムは見つかっていません。

ここで、「非負整数$n$以下の長さのハミルトン閉路は存在するか？」という問題の神託が存在する場合を考えましょう。
辺$e\in E$の重み（長さ）を$w(e)$と表記します。
元のグラフの辺の長さの合計について、
\begin{equation*}
W(G)=\sum_{e\in E}w(e)
\end{equation*}
と定義すると、$n$を変化させながら繰り返し神託を使うことにより、二分探索法の要領で、決定性チューリングマシンを用いて、$O(\log W(G))$時間で問題の答えが得られます⁴。

つまり、この神託機械で、ハミルトン閉路問題は多項式時間で解けることになります。

神託機械で解ける問題のクラス

このような、神託機械で解ける問題の「解きやすさ」を考えるとき、もともと解きたい問題の難しさに加えて、付属する神託でどのような問題が解けるか、ということも関係してきます。

神託$A$を用いることによって、クラス$B$のアルゴリズムで解ける問題が属するクラスを、$B^{A}$と表記します。
なお、神託$A$を用いて解ける問題のクラス$C$を使って、$B^{C}$と表記することもできます。

例えば、「非負整数$n$以下の長さのハミルトン閉路は存在するか？」を返す神託$A$を利用すれば、先述のように、決定性チューリングマシンを用いて、多項式時間でハミルトン閉路問題が解けるため、このような問題のクラスは、$P^{A}=P^{C}$と書けます（クラス$C$はNPだと思うんですけど自信がないので明確には書かないでおきます）。

「還元」の強さ

チューリング還元

問題$A$が問題$B$にチューリング還元（Turing reduction）可能であるとは、問題$B$を神託として用いることで、$A$が計算できることを言います。
このとき、神託の使用回数に制限はありません。

言い換えると、なんらかのクラスXが存在して、$A\in X^{B}$ならば、$A$が$B$にチューリング還元可能ということです。

これを、$A\le_{T} B$と表記します⁵。

多項式時間チューリング還元

問題$A$が問題$B$に多項式時間チューリング還元（polynomial-time Turing reduction）可能、あるいはクック還元（Cook reduction）可能であるとは、問題$B$を神託として用いることで、$A$が決定性チューリングマシンを用いて多項式時間で計算できることを言います。

これはチューリング還元の特殊な場合です。
言い換えると、$A\in P^{B}$ならば、$A$が$B$に多項式時間チューリング還元可能ということです。

これを、$A\le_{T}^{p} B$と表記します⁶。

多対一還元

問題$A$が問題$B$に多対一還元（many-one reduction）可能とは、問題$A$の入力を問題$B$の入力に変換できることを言います。

これを、$A\le_{m}B$と表記します⁷。

具体的には、問題$A, B$がYESとなる入力語の集合（つまり言語）をそれぞれ、$L_{A}, L_{B}$と定義します。
このとき、すべての$w_{A}\in L_{A}$に対して$f(w_{A})\in L_{B}$となる計算可能関数$f:L_{A}\rightarrow L_{B}$が存在する場合を、多対一還元可能と言います。

多対一還元はチューリング還元の特殊な場合です。なぜなら、

1. 問題$A$への入力語$w_{A}$を、関数$f$で問題$B$の入力語に変換する（$w_{B}=f(w_{A})$）。この操作はチューリングマシンで行う。
2. 神託で問題$B$の答えを得る
3. これは問題$A$の答えでもある

という手順で$A$の答えを得ることができるからです。
多対一還元では、チューリング還元とは異なり、神託は１回しか使用できません。

すなわち、多対一還元可能ならばチューリング還元可能です。逆は成り立ちません。

多項式時間多対一還元

問題$A$が問題$B$に多項式時間多対一還元（polynomial-time many-one reduction）可能、あるいはカープ還元（Karp reduction）可能とは、問題$A$の入力を問題$B$の入力に変換でき、かつその操作が決定性チューリングマシンを用いて多項式時間でできることを言います。

これを、$A\le_{m}^{p} B$と表記します。

これは多対一還元の特殊な場合です。
言い換えると、入力の変換を行う計算可能関数$f:L_{A}\rightarrow L_{B}$が、多項式時間で計算できるように決定性チューリングマシンで実装可能ならば、$A$が$B$に多項式時間多対一還元可能ということです。

例

例えば、先ほどのハミルトン閉路問題に関する例では、

• 神託機械で多項式時間で解ける
• 神託は複数回使っている

という２つを満たすので、多項式時間チューリング還元であるが多項式時間多対一還元ではない例です。

また、SATがNP完全であることを説明した記事では、

• 神託機械で多項式時間で解ける
• 神託は、最後に１回だけ使えば十分

という２つを満たすので、多項式時間チューリング還元かつ多項式時間多対一還元である例です。

---

1. 答えを記録するにしろ、どのみち一回は解かなきゃいけないから。 ↩︎
2. 与えられたグラフに、ハミルトン閉路（すべての頂点を１回だけ通り、出発点に戻ってくる経路）が存在するかを判定する問題。 ↩︎
3. その証明に「還元」の概念が使われているのですが、まあ気にしないでください。 ↩︎
4. すべての頂点をちょうど１回だけ通る、すなわち各辺は高々１回だけしか通れないという条件があるため、ハミルトン閉路の長さは、元のグラフの辺の長さの合計を上回ることはない。 ↩︎
5. $T$はおそらく、チューリング（Turing）の$T$です。 ↩︎
6. $p$はおそらく、多項式（polynomial）の$p$です。 ↩︎
7. $m$はおそらく、多対一（many-one）の$m$です。 ↩︎