「NP完全」における利用例
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/20 07:31 UTC 版)
「多項式時間変換」の記事における「「NP完全」における利用例」の解説
ある問題がNP完全問題であるかは次のようにして証明されてきた。まず、スティーブン・クックによって充足可能性問題 がNP完全であることが証明された。それ以外の NP完全問題は NP完全問題に属する問題 A は別の NPに属する問題 B に対して多項式時間変換可能であると分かった。 つまり B は A と同等かそれより難しい。 ところが NP完全問題とは NP に属する問題の中で一番難しい問題である。 つまり A より難しい NPに属する問題は存在しない。 よって B は A と同等すなわち B も NP完全問題である。 という論法で証明されている。
※この「「NP完全」における利用例」の解説は、「多項式時間変換」の解説の一部です。
「「NP完全」における利用例」を含む「多項式時間変換」の記事については、「多項式時間変換」の概要を参照ください。
ウィキペディア小見出し辞書の「「NP完全」における利用例」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- 「NP完全」における利用例のページへのリンク
