NP完全問題とは、計算複雑性理論における問題のクラスの一つで、「効率的に解くアルゴリズムが見つかっていないが、提示された解が正しいかを検証することは容易な問題」の中で最も難しい一群を指します。AIや巡回セールスマン問題などの組み合わせ最適化問題の計算コストを理解する上で、基礎となる重要な概念です。
NP完全問題とは
NP完全問題を一言でいうと、解答の検証は短時間でできるものの、正解を自力で見つけるには莫大な計算時間がかかると考えられている問題グループの中で、最も難易度が高い問題群のことです。
詳しく解説
計算理論では、問題を解くために必要な時間や計算量によってクラス分けを行います。短時間（多項式時間）で解ける問題を「P問題」、解の正しい検証が短時間でできる問題を「NP問題」と呼びます。NP完全問題はNP問題に含まれ、かつNP問題の中のあらゆる問題から効率よく変換できる性質を持ちます。そのため、NP完全問題のうちどれか1つでも効率的に解くアルゴリズムが発見されれば、すべてのNP問題が短時間で解ける（P=NP）ことになります。現代のAI分野においても、機械学習のハイパーパラメータ最適化や複雑なスケジューリングなどの基盤に深く関係しています。
具体例・使われ方
代表的な例として「巡回セールスマン問題」（複数の都市を一度ずつ訪問して戻る最短ルートを求める問題）や「分割問題」、「満たされやすさ問題（3-SAT）」などが挙げられます。AIの路線検索や物流のルート最適化、チップの回路設計など、現実世界の複雑な決定問題の多くがNP完全問題またはそれに関連するクラスに属しています。
似た用語との違い
NP完全問題は「NP問題」かつ「NP困難」の両方の性質を満たすものです。これに対し、「P問題」は効率的に解くことができる問題群であり、NP完全問題はP問題に含まれないと考えられています。また、「NP困難」はNP完全と同等以上に難しい問題全般を指し、答えの検証が容易である必要はありません。AIにおける広義の組み合わせ最適化問題には、NP困難に分類されるものも多く含まれます。
注意点
NP完全問題だからといって「絶対に解けない」という意味ではありません。入力のデータサイズが小さければ厳密解を高速に求められる場合があります。また、AIの応用分野では、厳密な最適解ではなく実用的な時間で十分に良い答えを得る「近似アルゴリズム」やメタヒューリスティクスを活用することで問題に対処するのが一般的です。