技術士試験ナビ

技術士試験対策・テキスト・過去問題解説を発信します。

技術士第一次試験専門科目 平成29年度 Ⅲ-2

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

(ア)NP問題とは,非決定性チューリングマシンにより,問題のサイズの多項式時間で解くことができる問題である。

(イ)NP問題とは,答えが与えられたとき,その答えが正しいかを,問題のサイズの多項式時間で判定できるアルゴリズムが存在する問題である。

(ウ)NP問題とは,決定性チューリングマシンにより,問題のサイズの多項式時間で解くことができない問題である。

(エ)NP問題であるがP問題ではない問題は存在するが,P問題であるがNP問題ではない問題は存在しない。

 

① (ア),(イ)

② (ア),(ウ)

③ (ア),(エ)

④ (イ),(ウ)

⑤ (イ),(エ)

 

 

答え

      ①

解説

 XXX

① XXX

② XXX

③ XXX

④ XXX

⑤ XXX