多項式時間変換のソースを表示

'''多項式時間変換'''（たこうしきじかんへんかん、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 (計算量理論)|P]] に属する問題に還元することはできそうにない程度には非力だからである。[[NP完全]]、[[PSPACE|PSPACE完全]]、[[EXPTIME|EXPTIME完全]]などの標準的な定義には、この還元可能性の概念を用いることが多い。

しかしながら、多項式時間還元はクラス [[P (計算量理論)|P]] の中で用いるには不適当である。何故なら P に属する如何なる問題も、P に属する他の殆ど全ての問題<ref>ここで「殆ど全て」というのは、他から多対一還元できない例外的な問題があるため（但しチューリング還元はできる）。その問題とは、如何なる入力でも肯定する問題と、同じく否定する問題である。これらを指して「自明な問題」と呼ぶ場合がある。</ref>に（多対一還元でもチューリング還元でも）多項式時間帰着できるからである。従って、P の中に存在するクラス（例えば[[NL (計算量理論)|NL]]、[[NC (計算量理論)|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完全問題は
# NP完全問題に属する問題 A は別の NPに属する問題 B に対して多項式時間変換可能であると分かった。
# つまり B は A と同等かそれより難しい。
# ところが NP完全問題とは NP に属する問題の中で一番難しい問題である。
# つまり A より難しい NPに属する問題は存在しない。
# よって B は A と同等すなわち B も NP完全問題である。
という論法で証明されている。

== 関連項目 ==
*[[対数領域還元]]

==脚注==
<references/>


{{DEFAULTSORT:たこうしきしかんへんかん}}
[[Category:還元 (計算複雑性理論)]]
[[Category:数学に関する記事]]

[[he:רדוקציה חישובית]]