IT資格用語解説応用情報技術者試験・計算量
NP 完全問題
更新日:
用語解説
NP完全問題は、NP問題の中で最も難しく、どのNP問題も多項式の時間でこの問題に変換できる問題です。
■ 試験で押さえるポイント
論理式の充足可能性問題（SAT）が最初に証明されました。
1つでも多項式の時間で解ければ、すべてのNP問題が多項式の時間で解けます。
NPに属さないものまで含めて、同じくらい難しい問題をNP困難問題といいます。
■ 過去問での着眼点
NP完全はNPに属し、NP困難はNPに属するとは限らない点を区別します。
例: ナップサック問題（判定の問題）はNP完全問題として知られています。