クラス NP に属する判定問題の性質として、適切なものはどれか。

解説

正解は「答えが Yes の根拠となる証拠が与えられれば、多項式時間で検証できる」です。例えば「長さの合計が K 以下の巡回路があるか」という問題では、巡回路が示されれば、長さを足して K と比べるだけで検証できます。これは、非決定性チューリング機械が証拠を推測して多項式時間で受理できることと同値です。P に属する問題はすべて NP にも属します。「必ず指数時間かかり、多項式時間では解けない」は誤りで、P の問題も NP に含まれます。「多項式時間では解けないことが証明されている」も誤りで、P ≠ NP かどうかは未解決です。「チューリング機械では解くことができない」も誤りで、NP の問題は全探索で必ず解けます。