# 多項式時間還元 ## 定義 多項式時間還元（polynomial-time reduction）とは、ある問題 A の任意のインスタンス x を、別の問題 B のインスタンス f(x) へと多項式時間で変換し、x in A <=> f(x) in B を満たす写像 f を構成することである（多対一還元 / カープ還元）。また、オラクル機械を用いて多項式時間計算の中で問題 B をサブルーチンとして呼び出す還元（チューリング還元 / クック還元）も含まれる。Cook（1971）および Karp（1972）によって導入され、問題間の相対的な計算困難性を厳密に比較・分類し、NP完全性を証明するための基本的道具として用いられる。(Source: [[@1971__STOC__The Complexity of Theorem-Proving Procedures]], [[@1972__ComplexityOfComputerComputations__Reducibility Among Combinatorial Problems]]) ## 未解決の問い - カープ還元（多対一多項式時間還元）とクック還元（チューリング多項式時間還元）の間でNP完全問題のクラスが一致するかどうか（分離の可能性）。 - 近似困難性（PCP定理以降の還元）におけるL還元やギャップ保存還元の限界。 ## 未編纂の観察 - ## 関連 - ソース: [[@1971__STOC__The Complexity of Theorem-Proving Procedures]]、[[@1972__ComplexityOfComputerComputations__Reducibility Among Combinatorial Problems]] - 概念: [[計算複雑性]] - 人物: [[Stephen A. Cook]]、[[Richard M. Karp]] ## 出典 - Stephen A. Cook, "The Complexity of Theorem-Proving Procedures", *STOC*, 1971. - Richard M. Karp, "Reducibility Among Combinatorial Problems", *Complexity of Computer Computations*, 1972.