翻訳と辞書
Words near each other
・ NPO法人汎太平洋フォーラム
・ NPO法人災害救助犬ネットワーク
・ NPO法人神戸国際ハーモニーアイズ協会
・ NPO法人空手道POINT&K.O.ルール協会
・ NPO立小学校
・ NPO高卒支援会
・ NPP ズヴェズダ
・ NPT (曖昧さ回避)
・ NP困難
・ NP完全
NP完全問題
・ NP少額短期保険
・ NQ (航空会社コード)
・ NR (オートバイ)
・ NR-1 (原子力深海潜航艇)
・ NR-23 (機関砲)
・ NRB日本理容美容専門学校
・ NRDガイド
・ NREG東芝不動産
・ NREM睡眠


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

NP完全問題 : ミニ英和和英辞書
NP完全問題[えぬぴーかんぜんもんだい]
=====================================
〔語彙分解〕的な部分一致の検索結果は以下の通りです。

: [かん]
 【名詞】 1. The End (book, film, etc.) 2. Finis
: [ぜん]
  1. (n,pref) all 2. whole 3. entire 4. complete 5. overall 6. pan 
全問 : [ぜんもん]
 (n) all the questions (in exam)
: [もん]
 【名詞】 1. problem 2. question 
問題 : [もんだい]
 【名詞】 1. problem 2. question 
: [だい]
  1. (n,vs) title 2. subject 3. theme 4. topic 

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予想が肯定されるなら、どちらも「多項式時間では解くことのできない問題」でしかなく、それらの問題に対してメタ・ヒューリスティックなどを適用することによってどこまで効率的に近似解を見つけられるか、多項式時間の内でどこまで小さな近似度近似アルゴリズムを設計できるかなどが主な論点となり、両者の違いが大きく出るような状況にはならないからである。

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「NP完全問題」の詳細全文を読む




スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.