NP完全問題
(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完全
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/01 16:46 UTC 版)
NPの中では「完全」な問題を意味する。つまりNPの中では最も解くのが難しい。
※この「NP完全」の解説は、「NP困難」の解説の一部です。
「NP完全」を含む「NP困難」の記事については、「NP困難」の概要を参照ください。
ウィキペディア小見出し辞書の「NP完全」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- NP完全のページへのリンク
