次の判定問題のうち、多項式時間で解けることが知られている（クラス P に属する）ものはどれか。

解説

正解は「重み0以上のグラフで、2頂点間の最短経路の長さが K 以下かを判定する問題」です。ダイクストラ法で、頂点数と辺数の多項式時間で最短経路の長さを求められるので、K と比較すれば判定できます。「各節が3つのリテラルからなる論理式を真にする割当てがあるかを判定する問題」は3-SAT で、NP 完全です（2つずつの 2-SAT なら多項式時間で解けます）。「すべての頂点を1回ずつ通る閉路がグラフにあるかを判定する問題」はハミルトン閉路問題で、NP 完全です。「整数の集合に、和がちょうど K になる部分集合があるかを判定する問題」は部分和問題で、これも NP 完全です。