多項式時間還元計算複雑性理論における問題の変換とクラス定義

計算複雑性理論において、ある問題を別の問題を利用して解決する手法を多項式時間還元（Polynomial-time reduction）と呼びます。これは、もし「問題B」を解く効率的なアルゴリズムが存在するならば、それを部品（サブルーチン）として利用することで「問題A」も効率的に解けることを証明する手法です。

具体的には、問題Aの入力を問題Bの入力形式に変換し、その結果をBの解法に渡します。この変換処理にかかる時間と、サブルーチンの呼び出し回数がともに多項式時間内である場合、問題Aは問題Bに多項式時間還元可能であると言えます。この概念は、問題同士の相対的な難易度を測定するための重要な尺度となります。

Key Facts

• 難易度の証明：AがBに還元可能であれば、AはBと同等か、それよりも簡単であることを意味します。
• 対偶の利用：Aに効率的な解法がないことが証明されていれば、Bにも効率的な解法は存在しません。
• クラスの定義：NP完全などの複雑性クラスや完全問題を定義するための基盤となります。
• 還元手法の多様性：制約の強さに応じて、多対一還元、真理値表還元、チューリング還元の3種類に大別されます。

還元の種類と特性

多項式時間還元には、その制約の厳しさに応じて主に3つの形式が存在します。一般的に、多対一還元が最も制約が強く、チューリング還元が最も汎用的です。

多対一還元（Many-one reduction）

カープ還元とも呼ばれるこの手法は、問題Aの入力を問題Bの入力へ1対1で変換します。変換後の問題Bの出力（Yes/No）が、そのまま元の問題Aの答えとなる形式です。記号では $A \le_{m}^{P} B$ または $A \le_{p} B$ と表記されます。

真理値表還元（Truth-table reduction）

問題Aの入力を、問題Bへの固定された複数の問い合わせに変換する手法です。問題Bから得られた複数の回答を、あらかじめ決められた真理値表（関数）に当てはめることで、最終的に問題Aの答えを導き出します。これは $A \le_{tt}^{P} B$ と表記されます。

チューリング還元（Turing reduction）

クック還元として知られるこの手法は、問題Bを解くサブルーチンを必要に応じて多項式回呼び出すアルゴリズムを用いて問題Aを解くものです。多対一還元は、サブルーチンの呼び出しが1回のみで、その結果をそのまま返すという特殊なケースのチューリング還元とみなせます。記号では $A \le_{T}^{P} B$ と表記されます。

還元形式	別名	特徴	制約の強さ
多対一還元	カープ還元	1つの入力を別の1つの入力に変換し、結果をそのまま利用	最も強い
真理値表還元	-	固定数の問い合わせを行い、真理値表に基づき判定	中間
チューリング還元	クック還元	サブルーチンとして柔軟に複数回呼び出し可能	最も緩い

完全性と複雑性クラスへの応用

ある複雑性クラス $C$ において、そのクラスに属するあらゆる問題が還元可能な問題 $P$ を、そのクラスの完全問題（Complete problem）と呼びます。例えば、NPに属し、かつNP内のすべての問題が多対一還元可能な問題は「NP完全」と定義されます。

すでにNP完全であることが分かっている問題から、未知の問題へ多項式時間還元ができれば、その未知の問題もNP完全であることが証明されます。この手法は、PSPACE完全やEXPTIME完全などの定義にも応用されています。

Pクラスにおける制限

興味深いことに、多項式時間還元はP（多項式時間で解ける決定問題のクラス）内部の完全性を定義するには不適切です。なぜなら、Pに属する任意の非自明な問題は、他のあらゆる非自明な問題に多項式時間還元できてしまうためです。そのため、P完全などの定義には、より制約の強い「対数領域還元（log-space reduction）」などが用いられます。

還元によるクラス定義

通常、NPやPSPACEなどのクラス定義に還元は使いませんが、還元そのものをベースにクラスを定義する場合もあります。例えば、$\exists \mathbb{R}$ というクラスは、「実数の存在理論」という問題に多項式時間多対一還元可能な問題の集合として定義されています。同様に、グラフ同型性問題に還元可能な問題の集合は GI クラスと呼ばれます。

Frequently Asked Questions

多項式時間還元を使うと何が分かるのですか？

2つの問題の相対的な難易度が分かります。問題Aが問題Bに還元可能であれば、「Bが効率的に解けるならAも効率的に解ける」ことが保証されるため、AはBより難しくないことが証明されます。

カープ還元とクック還元の違いは何ですか？

カープ還元（多対一還元）は、入力を1回だけ変換してBに問いかけ、その答えをそのまま使う非常にシンプルな形式です。一方、クック還元（チューリング還元）は、Bを関数のように何度も呼び出し、その結果を組み合わせてAの答えを導き出す柔軟な形式です。

なぜPクラスの完全問題に多項式時間還元を使えないのですか？

Pクラス内の問題はもともと多項式時間で解けるため、還元処理の中で問題を完全に解いてしまい、答えをBの形式に書き換えることが可能です。これにより、あらゆる問題が互いに還元可能になってしまい、問題間の難易度の差を区別できなくなるためです。

NP完全問題を証明する最も一般的な方法は？

まず、その問題がNPクラスに属することを示し、次に、すでにNP完全であると知られている別の問題から、その問題への多項式時間多対一還元を構築することで証明します。