クック・レビンの定理によって、最初に NP 完全であることが示された問題はどれか。

解説

正解は「充足可能性問題（SAT）」です。SAT は、論理変数からなる論理式に対して、式全体を真にする変数の値の割当てが存在するかを判定する問題です。クックとレビンは、非決定性チューリング機械の多項式時間の計算を論理式で表すことで、NP のすべての問題が SAT に多項式時間で帰着できることを示しました。その後、SAT からの帰着によって多くの問題の NP 完全性が示されました。「巡回セールスマン問題」の判定版も NP 完全ですが、後に帰着によって示されたものです。「グラフの最短経路問題」は、ダイクストラ法などで多項式時間で解ける P の問題です。「停止性問題」は決定不能で、NP にも属しません。