還元の「強さ」と「弱さ」
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/20 07:31 UTC 版)
「多項式時間変換」の記事における「還元の「強さ」と「弱さ」」の解説
多項式時間チューリング還元（Cook 還元）と 多項式時間多対一還元（Karp 還元）では、前者の方が道具としては「強い」。したがって、ある問題がある問題に「還元可能である」という主張は、後者の還元の意味で言ったときの方が強い。 例えば、co-NPに属する任意の問題は、任意のNP完全問題に Cook 還元できるのに対し、co-NP かつ NP である問題（があると仮定して）を NP に Karp 還元することは出来ない。Cook 還元のこの力は還元を設計する上では有用だが、短所として、NP などある種のクラスは Cook 還元の下で閉じているかどうかが判っていない（多分閉じていないだろうと考えられている）。従って、Cook 還元は、ある問題が NP に属すかどうかを証明する上では役に立たない（ただ、与えられた問題が Cook 還元の下で閉じていることが判っているクラス（例えば P など）に属するかどうかを示す上では役に立つ）。これに対し、ある問題を NP に属する問題に Karp 還元できる場合、元の問題は NP に属すると言える。従って Karp 還元によって得られる同値類の方が精度が高いので、Karp 還元の方が強い。
※この「還元の「強さ」と「弱さ」」の解説は、「多項式時間変換」の解説の一部です。
「還元の「強さ」と「弱さ」」を含む「多項式時間変換」の記事については、「多項式時間変換」の概要を参照ください。
ウィキペディア小見出し辞書の「還元の「強さ」と「弱さ」」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 還元の「強さ」と「弱さ」のページへのリンク
