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

Упражнение 1:

Номер 1

Машина Тьюринга, имеющая состояния, в которых она может выполнить одно из нескольких действий, называется:

Ответ:

(1) недетерминированной

(2) детерминированной

(3) переходной

Номер 3

Отличием недетерминированной машины Тьюринга является:

Ответ:

(1) наличие нескольких путей вычисления

(2) наличие функции переходов

(3) возможность выбора перехода на каждом такте работы

Номер 2

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

Ответ:

(1) класс NP определен только для предикатов

(2) NP - класс предикатов, вычислимых за полиномиальное время недетерминированными машинами Тьюринга

(3) недетерминированные машины Тьюринга имеют несколько путей вычисления

Упражнение 2:

Номер 1

Условие  для предиката , принадлежащего классу , означает, что:

Ответ:

(1) на любом пути вычисления ответа "да" не получается

(2) существует путь вычисления, дающий ответ "да" за время, не превосходящее math

(3) нет верного ответа

Номер 2

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

Ответ:

(1) существует путь вычисления, дающий ответ "да" за время, не превосходящее math

(2) не существует пути вычисления, дающий ответ "да" за время, не превосходящее math

(3) на любом пути вычисления ответа "да" не получается

Номер 3

Какое понятие используется для определения класса :

Ответ:

(1) понятие недетерминированной машины Тьюринга

(2) понятие полиномиально вычислимого предиката от одной переменной

(3) понятие полиномиально вычислимого предиката от двух переменных

Упражнение 3:

Номер 1

Предикат  принадлежит классу , если он представим в форме:

Ответ:

(1)

(2)

(3)

Номер 2

Под размером входа для предиката  в записи  понимают:

Ответ:

(1)

(2)

(3)

Номер 3

Для формы  справедливо:

Ответ:

(1)

- полином

(2)

(3)

Упражнение 4:

Номер 1

Условием полиномиальной сводимости предиката  к предикату  является:

Ответ:

(1) существование функции math

, что

(2) существование функции math

, что

(3) существование функции math

, что

Номер 2

Сводимость по Карпу предиката  к предикату  обозначается:

Ответ:

(1)

(2)

(3)

Номер 3

Если , то:

Ответ:

(1)

(2)

(3)

Упражнение 5:

Номер 1

Какая цепочка эквивалентностей является некорректной:

Ответ:

(1)

(2)

(3)

Номер 2

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

Ответ:

(1) следствием сходимости предиката math

к предикату math

является

(2) сводимость по Карпу называют полиномиальной сводимостью

(3) если любой предикат из math

сводится к math

, то предикат math

называется math

-полным

Номер 3

Если -полный предикат можно вычислить за время , то любой предикат из  для некоторого числа  можно вычислить за время:

Ответ:

(1)

(2)

(3)

Упражнение 6:

Номер 1

Предикатом  задается:

Ответ:

(1) выполнимость

(2) сложность

(3) сводимость

Номер 2

Авторами теоремы "Если , то "  являются:

Ответ:

(1) Черч

(2) Левин

(3) Кук

(4) Карп

Номер 3

Теорема Кука, Левина утверждает, что:

Ответ:

(1) если math

, то

(2) если math

, то

(3) если math

, то

Упражнение 7:

Номер 1

Справедливым является утверждение:

Ответ:

(1) если math

и

, то

- NP-полная

(2) нет верного ответа

(3) если math

- NP-полная, math

и

, то

- NP-полная

Номер 2

Проверка транзизитивности сводимости -  если , , то  является достаточным доказательством утверждения:

Ответ:

(1) если math

, то

(2) если math

, то

(3) если math

и

, то

- NP-полная

Номер 3

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

Ответ:

(1) NP-полные предикаты существуют

(2) композиция двух полиномиально вычислимых функций полиномиально вычислима

(3) NP-полные предикаты не существуют

Упражнение 8:

Номер 1

3-КНФ - это:

Ответ:

(1) конъюнкция отрицаний, каждая из которых содержит три литерала

(2) дизъюнкция конъюнкций, каждая из которых содержит три литерала

(3) конъюнкция дизъюнкций, каждая из которых содержит три литерала

Номер 2

Предикат, задающий 3-КНФ:

Ответ:

(1)

(2)

(3)

Номер 3

Справедливым является утверждение (запись):

Ответ:

(1)

является NP-полной

(2)

(3) 3-КНФ задается предикатом math

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