計算複雑性理論において、NP困難（NP-hard）とは、問題の複雑さのクラスの一つであり、「少なくともNP（Non-deterministic Polynomial time）に属する問題と同等以上に難しい」問題のクラスを指します。
NP困難の定義
NP困難な問題は、以下の性質を持ちます。
- NPに属する全ての問題から多項式時間帰着可能: つまり、NPに属する任意の問題を、多項式時間でNP困難な問題に変換できる。
- 必ずしも決定問題ではない: NPに属する問題は決定問題（Yes/Noで答えられる問題）ですが、NP困難な問題は最適化問題など、決定問題以外の問題も含まれます。
NP困難の重要性
NP困難な問題は、効率的な解法（多項式時間アルゴリズム）が存在する可能性が極めて低いと考えられています。もしNP困難な問題を多項式時間で解くアルゴリズムが見つかれば、NPに属する全ての問題も多項式時間で解けることになり、計算複雑性理論における最大の未解決問題である「P=NP問題」が解決されることになります。
代表的なNP困難な問題
- 巡回セールスマン問題（TSP）: 与えられた都市を全て一度ずつ訪問し、出発点に戻る最短経路を求める問題。
- ナップサック問題: 与えられた品物の中から、ナップサックの容量を超えない範囲で、価値の合計が最大となる組み合わせを求める問題。
- 充足可能性問題（SAT）: 与えられた論理式が真となる変数の組み合わせが存在するかどうかを判定する問題。
NP困難への対処
NP困難な問題に対しては、厳密な最適解を求めることが現実的でない場合が多いため、以下のような手法が用いられます。
- 近似アルゴリズム: 最適解に近い解を多項式時間で求めるアルゴリズム。
- ヒューリスティックアルゴリズム: 経験則に基づいて、比較的良い解を効率的に求めるアルゴリズム。
- メタヒューリスティクス: 遺伝的アルゴリズムや焼きなまし法など、より高度な探索手法。
NP困難な問題は、計算複雑性理論において重要な概念であり、現実世界の様々な問題に応用されています。これらの問題に対する効率的な解法を見つけることは、計算機科学における大きな課題の一つです。
