NP困難 - suto3の大福帳

NP困難

多項式時間変換 - 多対一還元やチューリング還元に計算時間の制限を付加したもの。

チューリング還元 - 計算時間を多項式時間に制限する場合は、それを示すために前に「多項式時間～」と付けるか、または Cook還元と呼ぶ。

多対一還元 - 計算時間を多項式時間に制限する場合は、それを示すために前に「多項式時間～」と付けるか、または Karp還元と呼ぶ。単に「多項式変換」と書けば通常 Karp還元を指す。