====== NP-完全 ======
==== NP-completeness ====

{{tag>..c17}}

　非決定性チューリング機械により多項式時間で解くことができる問題全体のクラスをNPというが，このクラスに属する問題の中で，もっとも難しい（もっとも長い計算時間を要する）問題のこと．厳密にいうと，アルファベット//Σ//上の問題（言語）がNP完全であるとは①\({\rm{A}} \in {\rm{NP}}\)，②NPに属する任意の問題Bに対しB≦Aの二つの条件がともに成り立つことである．ただし，②の関係における「≦」は多項式時間還元可能性（または，対数領域還元可能性，チューリング還元可能性）である．また，問題Aが（条件①の成否は問わないが）条件②を満たす時，AはNP困難であるという．問題AがNP完全であることを証明する方法は，定義通りに①および②が成り立つことを証明するか，①およびすでにNP完全であることが証明されている問題Bに対してB≦Aが成り立つことを証明するかである．NP完全問題の代表的な例として，巡回セールスマン問題，ナップザック問題，整数計画法の問題，クリーク問題などが知られている．これまで効率の良い解法を求めて多くの研究がなされてきたが，効率の良い解法が見い出されていない問題が数多く含まれている．


~~NOCACHE~~