令和7年度 III-5

解説

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

クラスNPの定義とPとNPの関係に関する4つの記述のうち、正しいものの組合せを選ぶ問題。

解き方

① NP=答えが与えられれば多項式時間で検証できる問題=非決定性チューリングマシンで多項式時間で解ける問題。P⊆NPだが、P≠NPかどうかは未解決
② (ア)は「NPだがPでない問題の存在が示されている」が未解決の問題なので×。(イ)は「解けない問題」と定義していて×。(ウ)(エ)は○
③ (ウ)・(エ)(⑤)

正解が正しい理由

(ア)クラスNPに属するがクラスPには属さない問題が存在するかどうか(P≠NP)は、2025年7月時点でも未解決であり、存在することが示されているとする記述は誤り。また、クラスPに属する問題は、すべてクラスNPにも属する(P⊆NP)ので、後半の記述は正しいが、前半が誤りのため全体として誤り。(イ)クラスNPは、多項式時間で「検証」できる問題のクラスであり、「決定性チューリングマシンで多項式時間で解けない問題」ではない。誤り。(ウ)クラスNPに属する問題とは、答え(証拠)が与えられたとき、その答えが正しいかを、問題のサイズの多項式時間で検証できるアルゴリズムが存在する問題である。正しい。(エ)クラスNPは、非決定性チューリングマシンにより、問題のサイズの多項式時間(非決定性多項式時間)で解くことができる問題のクラスとも定義される。正しい。したがって(ウ)、(エ)の⑤が正しい。

各選択肢について

• ① (ア)、(イ)はいずれも誤りである。
• ② (ア)は、P≠NPが未解決であるため誤り。
• ③ (イ)は、NPを「多項式時間で解けない問題」としており誤り。
• ④ (イ)が誤りであるため不適切。
• ⑤ (ウ)、(エ)が正しく、これが正答。

覚えるべきポイント

クラスNPは、多項式時間で答えを検証できる問題のクラスであり、非決定性チューリングマシンで多項式時間で解ける問題のクラスと同値。P⊆NP は成り立つが、P≠NP かどうかは未解決である。