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