多項式時間変換
(多項式時間還元 から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/20 07:31 UTC 版)
多項式時間変換（たこうしきじかんへんかん、polynomial-time reduction）は計算量理論の一概念である。多項式時間帰着（たこうしきじかんきちゃく）、多項式時間還元（たこうしきじかんかんげん）ともいう。幾つか種類があるが、内容的に多対一還元であれば、「多項式時間多対一還元」「Karp 還元」などとも呼ばれる。もし内容がチューリング還元であれば、「多項式時間チューリング還元」「Cook 還元」などと呼ばれる。
- ^ ここで「殆ど全て」というのは、他から多対一還元できない例外的な問題があるため（但しチューリング還元はできる）。その問題とは、如何なる入力でも肯定する問題と、同じく否定する問題である。これらを指して「自明な問題」と呼ぶ場合がある。
[続きの解説]
「多項式時間変換」の続きの解説一覧
- 1 多項式時間変換とは
- 2 多項式時間変換の概要
- 3 関連項目
- 多項式時間変換のページへのリンク
