NP完全問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/01/21 20:43 UTC 版)
NP完全（な）問題（エヌピーかんぜん（な）もんだい、英: NP-complete problem）とは、(1) クラスNP（英: Non-deterministic Polynomial）に属する決定問題（言語）で、かつ (2) クラスNPに属する任意の問題から多項式時間還元（帰着）可能なもののことである。条件 (2) を満たす場合は、問題の定義が条件 (1) を満たさない場合にも、NP困難な問題とよびその計算量的な困難性を特徴づけている。多項式時間還元の推移性から、クラスNPに属する問題で、ある一つのNP完全問題から多項式時間還元可能なものも、またNP完全である。現在発見されているNP完全問題の証明の多くはこの推移性によって充足可能性問題などから導かれている。充足可能性問題がNP完全であることは1971年、スティーブン・クックによって証明され[1]、R. M. カープの定義した多項式時間還元[2]によって多くの計算量的に困難な問題が NP 完全であることが示された。
- ^ （Stephen Cook (1971). "The Complexity of Theorem Proving Procedures". Proceedings of the third annual ACM symposium on Theory of computing. pp. 151–158.）
- ^ （Richard M. Karp (1972). "Reducibility Among Combinatorial Problems" (PDF). In R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. pp. 85–103.）
- ^ J.Kleinberg・E.Tardos『アルゴリズムデザイン』浅野孝夫ほか訳, 共立出版, 2008, 455ページ
- ^ David P.Williamson・Daivid B.Shmoys『近似アルゴリズムデザイン』浅野孝夫訳, 共立出版, 2015,21ページ
- ^ David P.Williamson・Daivid B.Shmoys『近似アルゴリズムデザイン』浅野孝夫訳, 共立出版, 2015, 43ページ
- ^ David P.Williamson・Daivid B.Shmoys『近似アルゴリズムデザイン』浅野孝夫訳, 共立出版, 2015,67ページ
- ^ 『チューリングの計算理論入門』講談社、2014年2月20日、189頁。
- ^ Tetris is Hard, Even to Approximate, Technical Report MIT-LCS-TR-865、 Ueda, Nobuhisa; Nagao, Tadaaki (1996), NP-completeness results for NONOGRAM via Parsimonious Reductions, Technical Report, Department of Computer Science, Tokyo Institute of Technology, TR96-0008、牟田 秀俊 (2005), “ぷよぷよはNP完全”, IEICE technical report. Theoretical foundations of Computing 105 (72): 39-44、水野 秀一; 田中 哲朗 (2008), “I.Q Intelligent QubeのNP完全性の証明”, 情報処理学会研究報告. GI, [ゲーム情報学] 28: 53-59
[続きの解説]
「NP完全問題」の続きの解説一覧
- 1 NP完全問題とは
- 2 NP完全問題の概要
- 3 参考文献
このページでは「ウィキペディア」からNP完全問題を検索した結果を表示しています。
Weblioに収録されているすべての辞書からNP完全問題を検索する場合は、下記のリンクをクリックしてください。
全ての辞書からNP完全問題を検索
Weblioに収録されているすべての辞書からNP完全問題を検索する場合は、下記のリンクをクリックしてください。
全ての辞書からNP完全問題を検索 - NP完全問題のページへのリンク
