Выберите верное утверждение:

(Ответ считается верным, если отмечены все правильные варианты ответов.)

Варианты ответа

класс языков, распознаваемых недетерминированными машинами, работающими на памяти $\calS$ , содержится в классе языков, распознаваемых детерминированными машинами, работающими на памяти $\poly(S)$ (Верный ответ)

по двум сложностным классам $\calX$ и $\calY$ можно определить класс $\calX^\calY$ таких языков, которые распознаются машинами из класса $\calX$ с оракулами из $\calY$ (Верный ответ)

$\mathrm{EXPTIME}$ - класс языков, вычислимых за экспоненциальное время $2^{\poly(n)}$ (Верный ответ)

Классические и квантовые вычисления

Выберите верное утверждение: