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