2018年02月19日

平成29年度 技術士第一次試験問題 情報工学部門 V−2

V−2
計算量に関する次の記述のうち、適切なものの組合せ
はどれか。

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

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



答えはこちら
タグ:NP問題
posted by ファーストマクロ at 20:35| Comment(0) | H29技術士一次試験(情報工学)