Если число ходов ограничено , а , то время работы машины Тьюринга ограничено:
(Отметьте один правильный вариант ответа.)
Варианты ответа
(Верный ответ)
Похожие вопросы
Условие существования вероятностной машины Тьюринга и полинома , причем машина заведомо остановится за время, не превосходящее , определяет, что:
Если - множество троек вида , где , , , (), то для выполняются условия:
Если , - неотрицательные операторы, , - их нулевые подпространства, причем , ненулевые собственные числа и не меньше , где - угол между и , то справедливым является равенство:
Если - множество троек вида описанием схемы - приближенная реализация в стандартном базисе, а (, - размер описания схемы). Тогда для выполняется:
Если имеется физически реализуемое преобразование , причем для любого чистого состояния выполняется свойство: , то для любого оператора справедливым является равенство ( - некоторая фиксированная матрица плотности на пространстве ):
Если получено дробей вида то вероятность того, что наименьшее общее кратное их знаменателей отлично от (равномерно распределенное на множестве случайное число):
Если существует квантовый алгоритм вычисления функции , работающий за время для некоторой константы , то функция
Чему равна суммарная длина и в формуле , которой должна удовлетворять квантовая схема , вычисляющая :
Состояние машины Тьюринга задается тройкой , где бесконечное слово в алфавите - это:
Для существующей недетерминированной машины Тьюринга, полинома и предиката L условие означает: