NP 完全問題の定義として、適切なものはどれか。

解説

正解は「NP に属し、かつ NP のすべての問題がその問題に多項式時間で帰着できる問題」です。NP 完全問題は NP の中で最も難しい問題といえ、1つでも多項式時間で解ければ、帰着を通じて NP のすべての問題が多項式時間で解けることになります。充足可能性問題（SAT）、ハミルトン閉路問題、巡回セールスマン問題の判定版、部分和問題などが代表例です。「NP に属するが、多項式時間で解けないことが証明された問題」は誤りで、そのような証明は知られていません。「NP のどの問題からも帰着できない問題」は定義と逆です。「P に属し、かつ NP にも属する問題」は単に P の問題で、P ≠ NP なら NP 完全ではありません。