NP完全問題とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > NP完全問題の意味・解説 

NP完全問題

(NP-completeness から転送)

出典: フリー百科事典『ウィキペディア(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 完全であることが示された。

NP困難との違い

NP困難 (: NP-hard) は「NP完全な問題と比べ、同等またはそれ以上に難しい」という意味である。一方、NP完全はあくまでNPに属する問題で、NP困難である問題は必ずしもNPに属さなくてもよいという違いがある。

一般にNP完全とNP困難は極めて混同されやすく、特にアルゴリズムを扱う本などでは、NP完全と表記しながらもNP困難の説明をしていたり、本来はNP困難ではあってもNP完全ではない問題を「NP完全の例」として挙げる物が多々ある。

これは定義をよく理解せずに議論していることが主な理由だが、多くのNP完全な問題は、組合せ最適化問題の問題例にコスト/ゲインの閾値を与えた決定問題として定義されていることも一因であろう。

NP完全な問題の例

以下の問題は、NP完全である。NP完全な問題はすべて同じ難しさというわけではなく、最適化問題に直したときに問題によって近似可能性が大きく異なることがある。

充足可能性問題
変数の集合 一覧・ カテゴリ



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「NP完全問題」の関連用語











NP完全問題のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



NP完全問題のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのNP完全問題 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS