多項式時間変換 - Wikipedia多項式時間変換（たこうしきじかんへんかん、polynomial-time reduction）は計算量理論の一概念である。多項式時間帰着（たこうしきじかんきちゃく）、多項式時間還元（たこうしきじかんかんげん）ともいう。幾つか種類があるが、内容的に多対一還元であれば、「多項式時間多対一還元」「Karp 還元」などとも呼ばれる。もし内容がチューリング還元であれば、「多項式時間チューリング還元」「Cook 還元」などと呼ばれる。 ある問題 A の各問題例を、別の問題 B の問題例に決定性チューリングマシンを用いて多項式時間で変換して答が同じにできるとき、「A は B に多項式時間変換可能である」といい、 と書く。 ただしここでの変換は A の入力内容に依存してはならない。つまり A という問題の全パターンが B に変換できなければいけない。 この概念は計算理論において問題の「難しさ」の度合いを測
