平成29年度 技術士第一次試験問題【専門科目】
【16】情報工学部門
V−2
計算量に関する次の記述のうち、適切なものの組合せ
はどれか。

(ア) NP問題とは、非決定性チューリングマシンに
 より、問題のサイズの多項式時間で解くことが
 できる問題である。
(イ) NP問題とは、答えが与えられたとき、その答え
 が正しいかを、問題のサイズの多項式時間で判定
 できるアルゴリズムが存在する問題である。
(ウ) NP問題とは、決定性チューリングマシンに
 より、問題のサイズの多項式時間で解くことができ
 ない問題である。
(エ) NP問題であるがP問題ではない問題は存在する
 が、P問題であるがNP問題ではない問題は存在しない。

 @ (ア)、(イ)
 A (ア)、(ウ)
 B (ア)、(エ)
 C (イ)、(ウ)
 D (イ)、(エ)



【正解】 @

P問題 (Polynomial 問題 = ) は、非決定性チューリングマシンに
より、問題のサイズの多項式時間で解くことができる問題である。
簡単に言うと、簡単に素早く解くことができる問題のことである。

NP問題 (Non-deterministic Polynomial) は、2つの定義がある。
(1)非決定性チューリングマシンにより、問題のサイズの多項式時間で
 解くことができる問題である。
(2) 答えが与えられたとき、その答えが正しいかを、問題のサイズの
 多項式時間で判定できるアルゴリズムが存在する問題である。

(ア) 正しい。
(イ) 正しい。
(ウ) 誤り。
(エ) P問題⊆NP問題の関係が成り立つが、
 P問題≠NP問題であることは証明されていない。
 従って、NP問題であるがP問題ではない問題は存在しない可能性が
 あるため、誤りである。

EXCELのマクロのご相談なら  ファーストマクロ  



V−1 目次 V−3
ファーストマクロ TOPページ