NP 困難（NP-hard）と NP 完全の関係について、正しい記述はどれか。

解説

正解は「NP 困難な問題のうち、NP に属するものが NP 完全である」です。NP 困難とは、NP のすべての問題がその問題に多項式時間で帰着できること、つまり NP のどの問題と比べても易しくないことを表し、その問題自身が NP に属するかは問いません。停止性問題や、最短の巡回路そのものを求める巡回セールスマン問題（最適化版）は NP 困難ですが、NP に属さないため NP 完全ではありません。「NP 完全な問題のうち、NP に属さないものが NP 困難である」は、NP 完全な問題は定義上すべて NP に属するので成り立ちません。「NP 困難な問題は、すべて NP に属する」と「NP 困難な問題は、すべて決定可能である」は、停止性問題が反例になります。