平成29年度 III-2

解説

この問題で問われていること

計算量クラスPとNPの定義と、両者の関係を確認する問題。

解き方

① P=決定性TMで多項式時間で解ける、NP=非決定性TMで多項式時間で解ける=答えが正しいかを多項式時間で確かめられる。P⊆NPだが、P≠NPかどうかは未解決
② ア・イはNPの定義どおり。ウは定義ではない。エは「NPだがPでない問題が存在する」と断定しており、未解決の問題を言い切っている
③ (ア)(イ)の①

正解が正しい理由

(ア)NP問題とは、非決定性チューリングマシンにより、問題のサイズの多項式時間で解くことができる問題である。これは正しい。(イ)NP問題とは、答え(証拠)が与えられたとき、その答えが正しいかを、多項式時間で判定(検証)できるアルゴリズムが存在する問題である。これも、NPの同値な定義で、正しい。(ウ)決定性チューリングマシンで多項式時間で解けない問題、というのは誤り(それは、Pに属さない問題であって、NPの定義ではない)。(エ)PはNPに含まれるので、P問題であるがNP問題ではない問題は存在しないが、NPであってPでない問題が存在するかどうかは、未解決(P≠NP予想)であり、存在すると断定できない。したがって、正しいのは(ア)と(イ)で、①が正しい。

各選択肢について

• ① (ア)と(イ)が、NP問題の適切な定義で、正しい。これが正答。
• ② (ウ)が誤り(NPは、決定性TMで多項式時間で解けない問題ではない)。
• ③ (エ)は、NPでPでない問題が存在すると断定しており、P≠NPは未解決なので、誤り。
• ④ (ウ)が誤り。
• ⑤ (エ)が誤り(P≠NPは、未解決問題)。

覚えるべきポイント

P=決定性TMで多項式時間で解ける問題、NP=非決定性TMで多項式時間で解ける問題(=解の検証が多項式時間でできる問題)。P⊆NPは自明だが、P=NPかどうかは未解決。