計算量に関する次の記述のうち，適切なものの組合せはどれか。
（ア）NP問題とは，非決定性チューリングマシンにより，問題のサイズの多項式時間で解くことができる問題である。
（イ）NP問題とは，答えが与えられたとき，その答えが正しいかを，問題のサイズの多項式時間で判定できるアルゴリズムが存在する問題である。
（ウ）NP問題とは，決定性チューリングマシンにより，問題のサイズの多項式時間で解くことができない問題である。
（エ）NP問題であるがP問題ではない問題は存在するが，P問題であるがNP問題ではない問題は存在しない。
① （ア），（イ）
② （ア），（ウ）
③ （ア），（エ）
④ （イ），（ウ）
⑤ （イ），（エ）
答え
①
解説
XXX
（ア）NP問題とは，非決定性チューリングマシンにより，問題のサイズの多項式時間で解くことができる問題である。
適切です。
（イ）NP問題とは，答えが与えられたとき，その答えが正しいかを，問題のサイズの多項式時間で判定できるアルゴリズムが存在する問題である。
適切です。
（ウ）NP問題とは，決定性チューリングマシンにより，問題のサイズの多項式時間で解くことができない問題である。
XXXであるため、不適切です。
（エ）NP問題であるがP問題ではない問題は存在するが，P問題であるがNP問題ではない問題は存在しない。
XXXであるため、不適切です。