多項式時間変換

多項式時間変換（たこうしきじかんへんかん、polynomial-time reduction）は計算量理論の一概念である。多項式時間帰着（たこうしきじかんきちゃく）、多項式時間還元（たこうしきじかんかんげん）ともいう。幾つか種類があるが、内容的に多対一還元であれば、「多項式時間多対一還元」「Karp 還元」などとも呼ばれる。もし内容がチューリング還元であれば、「多項式時間チューリング還元」「Cook 還元」などと呼ばれる。

概要

ある問題 A の各問題例を、別の問題 B の問題例に決定性チューリングマシンを用いて多項式時間で変換して答が同じにできるとき、「A は B に多項式時間変換可能である」といい、 [math]A \leq_p B[/math] と書く。 ただしここでの変換は A の入力内容に依存してはならない。つまり A という問題の全パターンが B に変換できなければいけない。

この概念は計算理論において問題の「難しさ」の度合いを測る上でよく使われる。 A が B に多項式時間還元可能である場合、B を解くアルゴリズムがあれば、それを応用して A も解ける（この逆は成り立たない）。つまり B は A と同等かそれより難しいと結論できる。また、[math]A \leq_p B[/math] かつ [math]B \leq_p A[/math] である場合、A と B は多項式時間同値であると言い、[math]A \equiv_p B[/math] と書く。このとき A と B は同等の難しさを持つ。

多項式時間還元は重要で広く使われている。何故なら重要な問題同士を互いに変換できる程度には強力で、かつ、NPまたはco-NPに属する問題を P に属する問題に還元することはできそうにない程度には非力だからである。NP完全、PSPACE完全、EXPTIME完全などの標準的な定義には、この還元可能性の概念を用いることが多い。

しかしながら、多項式時間還元はクラス P の中で用いるには不適当である。何故なら P に属する如何なる問題も、P に属する他の殆ど全ての問題に（多対一還元でもチューリング還元でも）多項式時間帰着できるからである。従って、P の中に存在するクラス（例えばNL、NC や P 自身）については、代わりに対数領域還元が用いられる。

還元の「強さ」と「弱さ」

多項式時間チューリング還元（Cook 還元）と 多項式時間多対一還元（Karp 還元）では、前者の方が道具としては「強い」。したがって、ある問題がある問題に「還元可能である」という主張は、後者の還元の意味で言ったときの方が強い。

例えば、co-NPに属する任意の問題は、任意のNP完全問題に Cook 還元できるのに対し、co-NP かつ NP である問題（があると仮定して）を NP に Karp 還元することは出来ない。Cook 還元のこの力は還元を設計する上では有用だが、短所として、NP などある種のクラスは Cook 還元の下で閉じているかどうかが判っていない（多分閉じていないだろうと考えられている）。従って、Cook 還元は、ある問題が NP に属すかどうかを証明する上では役に立たない（ただ、与えられた問題が Cook 還元の下で閉じていることが判っているクラス（例えば P など）に属するかどうかを示す上では役に立つ）。これに対し、ある問題を NP に属する問題に Karp 還元できる場合、元の問題は NP に属すると言える。従って Karp 還元によって得られる同値類の方が精度が高いので、Karp 還元の方が強い。

「NP完全」における利用例

ある問題がNP完全問題であるかは次のようにして証明されてきた。まず、スティーブン・クックによって充足可能性問題 がNP完全であることが証明された。それ以外の NP完全問題は

1. NP完全問題に属する問題 A は別の NPに属する問題 B に対して多項式時間変換可能であると分かった。
2. つまり B は A と同等かそれより難しい。
3. ところが NP完全問題とは NP に属する問題の中で一番難しい問題である。
4. つまり A より難しい NPに属する問題は存在しない。
5. よって B は A と同等すなわち B も NP完全問題である。

という論法で証明されている。

関連項目

• 対数領域還元