技術士第一次試験 専門科目情報工学部門 R07

計算量に関する(ア)〜(エ)の記述のうち、正しいものの組合せはどれか。

 

(ア) 2025年7月において、クラスNPに属するがクラスPには属さない問題が存在することが示されているが、クラスPに属するがクラスNPには属さない問題は存在しない。

(イ) クラスNPに属する問題とは、決定性単一テープチューリングマシンにより、問題のサイズの多項式時間で解くことができない問題である。

(ウ) クラスNPに属する問題とは、答えが与えられたとき、その答えが正しいかを、問題のサイズの多項式時間で検証できるアルゴリズムが存在する問題である。

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