多項式時間変換

出典: フリー百科事典『ウィキペディア（Wikipedia）』

多項式時間変換（たこうしきじかんへんかん、polynomial-time reduction）は計算複雑性理論の一概念である。多項式時間帰着（たこうしきじかんきちゃく）、多項式時間還元（たこうしきじかんかんげん）ともいう。「時間」を省略して多項式変換と表記することもある。

[編集] 概要

ある問題 A の各問題例を別の問題 B の問題例に多項式時間で変換できるとき、「A は B に多項式時間変換可能である」という。ただしここでの変換は A の入力の内容に依存しないこととする、つまり A という問題に対する全ての問題のパターンが B に変換できなければいけない。

この概念は計算理論において問題の「難しさ」の度合いとしてよく使われる。すなわち、A が B に多項式時間変換可能なら A を解くアルゴリズムがあってもそれ用いて B を解くことができるか分からないが、 B を解くアルゴリズムがあれば、その変換を用いれば A は自動的に解ける。つまり B は A と同等かそれより難しいと結論することができるからである。

また完全性の証明にもよく使われる、例えばNP完全問題は NP完全であることの証明はスティーブン・クックによって充足可能性問題のみに行われた。それ以外の NP完全問題は