Главная /
Классические и квантовые вычисления /
Для существующей недетерминированной машины Тьюринга, полинома [формула] означает:
Для существующей недетерминированной машины Тьюринга, полинома ![math]()
и предиката L условие ![math]()
означает:
вопрос
и предиката L условие 
означает:Правильный ответ:
существует путь вычисления, дающий ответ "да" за время, не превосходящее ![math]()
не существует пути вычисления, дающий ответ "да" за время, не превосходящее ![math]()
на любом пути вычисления ответа "да" не получается
Сложность вопроса
53
Сложность курса: Классические и квантовые вычисления
49
Оценить вопрос
Комментарии:
Аноним
Это очень намудрённый решебник по интуиту.
17 мар 2018
Аноним
Благодарю за подсказками по intuit.
04 мар 2018
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
-
#
Каким преобразованием задается отбрасывание второй системы, если есть
![math]()
:
-
#
Условные вероятности для оператора
![math]()
определяются, как (![math]()
- значение в ![math]()
-ом бите):
- # Состояние перехода вероятностной машины Тьюринга определяется:
-
#
В формуле
![math]()
, которой должна удовлетворять квантовая схема ![math]()
, вычисляющая ![math]()
, значение ![math]()
:
- # Чему эквивалентно условие
: 
определяются, как (
- значение в 
-ом бите): 
, которой должна удовлетворять квантовая схема 
, вычисляющая 
, значение 
: