計算量に関する (ア) ～ (エ) の記述のうち、正しいものの組合せはどれか。
(ア) 2025年7月において、クラスNPに属するがクラスPには属さない問題が存在することが示されているが、クラスPに属するがクラスNPには属さない問題は存在しない。
(イ) クラスNPに属する問題とは、決定性単一テープチューリングマシンにより、問題のサイズの多項式時間で解くことができない問題である。
(ウ) クラスNPに属する問題とは、答えが与えられたとき、その答えが正しいかを、問題のサイズの多項式時間で検証できるアルゴリズムが存在する問題である。
(エ) クラスNPに属する問題とは、非決定性チューリングマシンにより、問題のサイズの非決定性多項式時間で解くことができる問題である。
① (ア)、(イ)
② (ア)、(ウ)
③ (イ)、(ウ)
④ (イ)、(エ)
⑤ (ウ)、(エ)
⑤
P問題 (Polynomial 問題) は、決定性チューリングマシンにより、問題のサイズの多項式時間で解くことができる問題である。簡単に言うと、簡単に素早く解くことができる問題のことである。
NP問題 (Non-deterministic Polynomial 問題) は、2つの定義がある。
(1) 非決定性チューリングマシンにより、問題のサイズの多項式時間で解くことができる問題である。
(2) 答えが与えられたとき、その答えが正しいかを、問題のサイズの多項式時間で判定できるアルゴリズムが存在する問題である。
(ア) P問題 ⊆ NP問題の関係が成り立つが、P問題 ≠ NP問題であることは証明されていない。従って、NP問題であるがP問題ではない問題は存在しない可能性がある。
また、P問題であるがNP問題ではない問題は存在せず、P問題であれば必ずNP問題である。
(イ) 誤りである。
(ウ) 正しい。
(エ) 正しい。
| Ⅲ－４ | 目次 | Ⅲ－６ |