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
- 1 NP完全問題とは
- 2 NP完全問題の概要
- 3 参考文献
NP完全
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/01 16:46 UTC 版)
NPの中では「完全」な問題を意味する。つまりNPの中では最も解くのが難しい。
※この「NP完全」の解説は、「NP困難」の解説の一部です。
「NP完全」を含む「NP困難」の記事については、「NP困難」の概要を参照ください。
NP完全
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/16 08:14 UTC 版)
1971年にスティーブン・クックが定式化した概念で、クラスNPに属し、クラスNPに属する他の全問題が多項式時間帰着される問題をNP完全という。充足可能性問題をはじめとして、数千個以上の問題がNP完全であることが示されている。これらのNP完全問題の一つでもクラスPに属することを示せれば、P＝NPとなる。
※この「NP完全」の解説は、「P≠NP予想」の解説の一部です。
「NP完全」を含む「P≠NP予想」の記事については、「P≠NP予想」の概要を参照ください。
NP完全
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/07/22 07:19 UTC 版)
充足可能性問題はNP（Non-deterministic Polynomial time（非決定性多項式時間）非決定性チューリングマシンによって多項式時間で解くことができる問題）かつNP困難な問題である。このような問題のクラスをNP完全問題という。充足可能性問題を多項式時間で変形することによって、様々なNP完全問題を構成することができる。 任意の論理式からなる充足可能性問題はNP完全であるが、ある特殊な形状をもつ論理式のクラスに限定しても、なおNP完全であることが証明されている。 CNF-SAT - 節の論理積からなるもの。 3-SAT - CNF-SATのうち、節内のリテラル数が、高々3つのもの。 NP問題の補問題、つまり結果のYesとNoを逆転させた問題をco-NP問題という。 充足可能性問題のYesとNoを逆転させ、論理式に否定をかけて変形すると、トートロジー判定問題になる。トートロジー判定問題はco-NP完全問題である。
※この「NP完全」の解説は、「充足可能性問題」の解説の一部です。
「NP完全」を含む「充足可能性問題」の記事については、「充足可能性問題」の概要を参照ください。
- NP完全のページへのリンク
