コンテンツにスキップ
メインメニュー
メインメニュー
サイドバーに移動
非表示
案内
メインページ
最近の更新
おまかせ表示
MediaWiki についてのヘルプ
特別ページ
Wikippe
検索
検索
表示
ログイン
個人用ツール
ログイン
NP完全問題のソースを表示
ページ
議論
日本語
閲覧
ソースを閲覧
履歴を表示
ツール
ツール
サイドバーに移動
非表示
操作
閲覧
ソースを閲覧
履歴を表示
全般
リンク元
関連ページの更新状況
ページ情報
表示
サイドバーに移動
非表示
←
NP完全問題
あなたには「このページの編集」を行う権限がありません。理由は以下の通りです:
要求した操作を行うことは許可されていません。
このページのソースの閲覧やコピーができます。
'''NP完全問題'''(エヌピーかんぜんもんだい、NP-complete problem)は、クラス[[NP]](Non-deterministic Polynomial)に属する問題でかつ、クラス[[NP]]のすべての問題から[[多項式時間変換|多項式時間帰着]]可能な問題である。すなわち、NPに属する問題のうちで[[NP困難]]なものである。クラスNPに含まれる問題で、あるNP完全問題から多項式時間還元可能なものも、またNP完全である。現在発見されているNP完全問題の多くがこの定理によって[[充足可能性問題]]より導かれたものである。[[充足可能性問題]]がNP完全であることは[[1971年]]、[[スティーブン・クック]]によって証明された。 == NP困難との違い == '''[[NP困難]](NP-hard)'''は「[[NP]]に属する問題と比べ、同等以上に難しい」という意味である。一方、'''NP完全'''はあくまでNPに属する最も難しい問題なので、NP困難はNP完全と同等以上に難しい。定義上、NP困難である問題は必ずしもNPに属さなくても良いが、たまたまNPにも属する場合はNP完全と一致する。 一般にNP完全とNP困難は極めて混同されやすく、特に[[アルゴリズム]]を扱う本などでは、NP完全と表記しながらもNP困難の説明をしていたり、本来はNP困難ではあってもNP完全ではない問題を「NP完全の例」として挙げる物が多々ある。 この理由の一つとしては、大抵のNP完全問題は別のNP困難な問題の特殊なケースであることが多いためである。 もう一つの理由としてはNP完全とNP困難は[[計算量理論]]の研究者にとっては重要な違いではあるが、[[アルゴリズム論]]の研究者にはそれほど重要な違いではないためである。アルゴリズム論の研究者にとっては[[P≠NP予想]]が肯定されるなら、どちらも「[[多項式時間]]では解くことのできない問題」でしかなく、それらの問題に対して[[メタ・ヒューリスティック]]などを適用することによってどこまで効率的に近似解を見つけられるか、多項式時間の内でどこまで小さな[[近似度]]の[[近似アルゴリズム]]を設計できるかなどが主な論点となり、両者の違いが大きく出るような状況にはならないからである。 == NP完全問題の例 == 以下の問題は、適当に判定問題の形にして考えると、NP完全である。 *[[充足可能性問題]] *[[頂点被覆問題]] *[[ハミルトン閉路問題]] *[[部分和問題]] *[[行商人問題]] *[[ナップサック問題]] *[[テトリス]]をはじめとした様々なパズルゲーム<ref>{{citation|title=Tetris is Hard, Even to Approximate|first=Erik D. last=Demaine|coauthors= Susan Hohenberger, David Liben-Nowell|id=Technical Report MIT-LCS-TR-865}}</ref><ref> {{Citation|first1=Nobuhisa|last1=Ueda|first2=Tadaaki|last2=Nagao|title=NP-completeness results for NONOGRAM via Parsimonious Reductions|year=1996|place=Technical Report, Department of Computer Science, Tokyo Institute of Technology|id=TR96-0008}}</ref><ref>{{citation|title=ぷよぷよはNP完全|author=牟田 秀俊|journal=IEICE technical report. Theoretical foundations of Computing|volume=105|number=72|pages=39-44|year=2005}}</ref><ref>{{citation|title=I.Q Intelligent QubeのNP完全性の証明|author=水野 秀一|coauthors=田中 哲朗|journal=情報処理学会研究報告. GI, [ゲーム情報学] |year=2008|volume=28|pages=53-59}}</ref> == 註 == <references /> {{DEFAULTSORT:えぬひいかんせんもんたい}} [[Category:計算複雑性理論]] [[Category:数学の問題]] [[Category:数学に関する記事|NPえぬひいかんせんもんたい]]
このページで使用されているテンプレート:
テンプレート:Citation
(
ソースを閲覧
)
NP完全問題
に戻る。
検索
検索
NP完全問題のソースを表示
話題を追加