|
多項式時間変換（たこうしきじかんへんかん、polynomial-time reduction）は計算量理論の一概念である。多項式時間帰着（たこうしきじかんきちゃく）、多項式時間還元（たこうしきじかんかんげん）ともいう。幾つか種類があるが、内容的に多対一還元であれば、「多項式時間多対一還元」「Karp 還元」などとも呼ばれる。もし内容がチューリング還元であれば、「多項式時間チューリング還元」「Cook 還元」などと呼ばれる。 == 概要 == ある問題 A の各問題例を、別の問題 B の問題例に決定性チューリングマシンを用いて多項式時間で変換して答が同じにできるとき、「A は B に多項式時間変換可能である」といい、 と書く。 ただしここでの変換は A の入力内容に依存してはならない。つまり A という問題の全パターンが B に変換できなければいけない。 この概念は計算理論において問題の「難しさ」の度合いを測る上でよく使われる。 A が B に多項式時間還元可能である場合、B を解くアルゴリズムがあれば、それを応用して A も解ける（この逆は成り立たない）。つまり B は A と同等かそれより難しいと結論できる。また、 かつ である場合、A と B は多項式時間同値であると言い、 と書く。このとき A と B は同等の難しさを持つ。 多項式時間還元は重要で広く使われている。何故なら重要な問題同士を互いに変換できる程度には強力で、かつ、NPまたはco-NPに属する問題を P に属する問題に還元することはできそうにない程度には非力だからである。NP完全、PSPACE完全、EXPTIME完全などの標準的な定義には、この還元可能性の概念を用いることが多い。 しかしながら、多項式時間還元はクラス P の中で用いるには不適当である。何故なら P に属する如何なる問題も、P に属する他の殆ど全ての問題〔ここで「殆ど全て」というのは、他から多対一還元できない例外的な問題があるため（但しチューリング還元はできる）。その問題とは、如何なる入力でも肯定する問題と、同じく否定する問題である。これらを指して「自明な問題」と呼ぶ場合がある。〕に（多対一還元でもチューリング還元でも）多項式時間帰着できるからである。従って、P の中に存在するクラス（例えばNL、NC や P 自身）については、代わりに対数領域還元が用いられる。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「多項式時間変換」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Polynomial-time reduction 」があります。 スポンサード リンク
|