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

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

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

Условием разрешимости предиката является:

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

Варианты ответа
характеристическая функция вычислима(Верный ответ)
характеристическая функция равна 0
характеристическая функция равна 1
Похожие вопросы
Условием полиномиальной сводимости предиката L_1 к предикату L_2 является:
Условием выхода из алгоритма проверки простоты числа является:
Условием строгой формулировки вычислительной задачи является наличие:
Условием остановки машины Тьюринга, находящейся в состоянии (\sigma,p,q), является:
В контексте квантовой постановки нерешаемость задачи для любого предиката \calA(x,y) на квантовой схеме, означает, что:
Условием алгоритма проверки простоты числа n, определяющим что n - составное, где a - случайное среди чисел от 1 до n, l - нечетное, является:
За какое время квантовый компьютер вычислит значение предиката F(x)\double=\exists\, y\:\calA(x,y) (N - количество шагов):
Если характеристическая функция предиката вычислима на машине Тьюринга М, для которой S_М(n)=\poly(n), то
Для существующей недетерминированной машины Тьюринга, полинома p(n) и предиката L условие L(x)=0 означает:
Под размером входа для предиката R(x,y) в записи L(x)=\exists\, y\:\big( (|y|<q(|x|))\:\wedge\: R(x,y)\big) понимают: