本文へスキップ

技術士試験(情報工学部門)・情報技術者試験。ファーストマクロ。


Since 2016.4.19

平成29年度 技術士第一次試験問題【専門科目】

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問題ではない問題は存在しない可能性があるため、誤りである。

V−1 目次 V−3