NP完全
NP完全（NP-complete）とは、計算理論における重要なクラスの一つであり、NP-hardかつNPに属する問題のことを指します。つまり、NP完全な問題は、以下の2つの性質を持ちます。
- NP-hard：多項式時間内に他のどのNP問題でも解くことができる（NP-hard問題と同様）。
- NPに属する：多項式時間で検証可能な解が存在する（つまり、解の候補が与えられたときに、その解が正しいかどうかを多項式時間で確認できる）。
NP完全な問題は、多項式時間で解くことができるアルゴリズムが見つかれば、すべてのNP問題を効率的に解くことができます。しかし、NP完全問題の中でも特に難しい問題は、現在のところ多項式時間で解くことができるアルゴリズムが知られていません。
代表的なNP完全な問題には、3SAT（3つの変数を持つ論理積標準形の充足可能性問題）、巡回セールスマン問題、ナップサック問題などがあります。これらの問題は、実用的な観点から非常に重要であり、多くの現実世界の問題をモデル化するために使用されています。
NP完全性の概念は、計算理論やアルゴリズム設計において重要な役割を果たしています。NP完全な問題に対する解法の発見は、計算の難しさに関する理解を深め、効率的なアルゴリズムの設計に寄与します。