База ответов ИНТУИТ

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

<<- Назад к вопросам

Функции, которые могут быть вычислены на машине Тьюринга, использующей память, ограниченную полиномом от длины входного слова относятся к классу:

(Отметьте один правильный вариант ответа.)

Варианты ответа
\BPP
\PSPACE(Верный ответ)
\NP
Похожие вопросы
Важнейшими ресурсами, требующимися машине Тьюринга для вычислений, является:
Какому классу принадлежит L, если существует такая игра с полиномиальным от длины входного слова числом ходов и полиномиально вычислимым результатом, что L=\{x\:\big| Б имеет выигрышную стратегию \}(Б - игрок, имеющих имя "белые"):
Если характеристическая функция предиката вычислима на машине Тьюринга М, для которой S_М(n)=\poly(n), то
Количество состояний системы, где S - память, \callQ,\calA - соответственно множество состояний управляющего устройства и алфавит рассматриваемой машины Тьюринга, определяется по формуле:
Частичная функция f из \calA^* в \calA^* вычислима на машине Тьюринга :
Отличием недетерминированной машины Тьюринга является:
Время работы машины Тьюринга определяется:
Для вероятностной машины Тьюринга можно определить:
Состояние перехода вероятностной машины Тьюринга определяется:
Для задания состояния машины Тьюринга обязательным является указание: