計算量に関する次の記述のうち、適切なものの組合せ
はどれか。
(ア) ＮＰ問題とは、非決定性チューリングマシンに
より、問題のサイズの多項式時間で解くことが
できる問題である。
(イ) ＮＰ問題とは、答えが与えられたとき、その答え
が正しいかを、問題のサイズの多項式時間で判定
できるアルゴリズムが存在する問題である。
(ウ) ＮＰ問題とは、決定性チューリングマシンに
より、問題のサイズの多項式時間で解くことができ
ない問題である。
(エ) ＮＰ問題であるがＰ問題ではない問題は存在する
が、Ｐ問題であるがＮＰ問題ではない問題は存在しない。
① (ア)、(イ)
② (ア)、(ウ)
③ (ア)、(エ)
④ (イ)、(ウ)
⑤ (イ)、(エ)
Ｐ問題 (Polynomial 問題 = ) は、非決定性チューリングマシンに
より、問題のサイズの多項式時間で解くことができる問題である。
簡単に言うと、簡単に素早く解くことができる問題のことである。
ＮＰ問題 (Non-deterministic Polynomial) は、２つの定義がある。
(1)非決定性チューリングマシンにより、問題のサイズの多項式時間で
解くことができる問題である。
(2) 答えが与えられたとき、その答えが正しいかを、問題のサイズの
多項式時間で判定できるアルゴリズムが存在する問題である。
(ア) 正しい。
(イ) 正しい。
(ウ) 誤り。
(エ) Ｐ問題⊆ＮＰ問題の関係が成り立つが、
Ｐ問題≠ＮＰ問題であることは証明されていない。
従って、ＮＰ問題であるがＰ問題ではない問題は存在しない可能性が
あるため、誤りである。
EXCELのマクロのご相談なら ファーストマクロ へ
タグ：ＮＰ問題
