計算複雑性の理論におけるクラス P の説明として、適切なものはどれか。

解説

正解は「決定性チューリング機械で、入力サイズの多項式時間で解ける判定問題のクラス」です。入力サイズ n に対して、ある定数 k で $O(n^k)$ 時間で Yes か No を答えられる問題が P に属し、一般に効率よく解ける問題とみなされます。整列や最短経路問題、2部グラフの判定などが例です。「非決定性チューリング機械で、多項式時間で解ける判定問題のクラス」はクラス NP の定義です。「解の検証に指数時間を要する判定問題のクラス」は P の説明ではありません。NP は逆に、解の候補が与えられれば多項式時間で検証できるクラスです。「どのアルゴリズムでも解くことができない判定問題のクラス」は決定不能問題の説明です。