Тест по сложности алгоритмов для 3 курса ИСПРАН — вопросы

Найдите неверное утверждение:

Выберите не NP-полную задачу

Пусть задача A — «есть ли цикл в ненаправленном графе». Рассмотрим набор утверждений.

• (1) Задача A — в P
• (2) Задача A — в NP
• (3) Если задача A — NP-полна, то существует НМТ, решающая A за полиномиальное время.

Что верно?

Рассмотрим модификацию задачи «Сумма размеров», разрешим даже отрицательные размеры.

Формально: Даны натуральные числа , , и число B.

Надо узнать, существует ли решение в 0/1 переменных уравнения .

Существует ли полиномиальный алгоритм для этой задачи?

Какой класс ошибок допускают алгоритмы решающие задачи из класса ZPP?

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

Какое утверждение неверно?

Какой прием используется в FPTAS-алгоритме для рюкзака?

Аню и Колю попросили показать, что задача X — NP-полна. Аня показала полиномиальную сводимость по Карпу от 3SAT к X, а Коля показал полиномиальную сводимость по Карпу от X к 3SAT.

Что можно утверждать?

Пусть

• — задача поиска гамильтонового цикла в графе , где V — делится на 3.
• — задача подтверждения наличия гамильтонового цикла в таком графе.

Что верно?

Какой из этих тестов на простоту не является рандомизированным:

Предположим, открыли полиномиальный алгоритм, вычисляющий наибольшую клику в заданном графе. Что тогда будет, согласно вариантам на картинке?

Будет ли класс -полных задач замкнутым относительно сводимости по Карпу, если окажется, что ?

Существует ли биекция между классами и ?

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

Рассмотрим пару задач на графах.

P1

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

P2

Для заданного графа, подтвердить или опровергнуть, что в нем есть цикл, который проходит по каждому ребру точно один раз, без исключений.

Какие из подходов к решению вычислительно трудных задач изучались в курсе?

Вероятностные «zero-error»-алгоритмы:

Сложность алгоритма динамического программирования для задачи о рюкзаке, который «помнит» о наиболее «дорогих» допустимых решениях:

Замкнутость по какой из операций выполнена как для разрешимых, так и для перечислимых языков?

Предположим, разумеется, что Тогда что будет верно?

Задачи 3SAT и 2SAT:

Найдите неверное утверждение:

Какой класс ошибок допускают алгоритмы решающие задачи из класса PP?

Пусть X — задача из NP. Что верно?

Рассмотрим две задачи разрешения, P1 и P2, такие что

• P1 сводится полиномиально по Карпу к 3SAT
• 3SAT сводится полиномиально по Карпу к P2

Что можно утверждать?

С какой точностью работает «чисто» жадный алгоритм для задачи о рюкзаке («хватать предметы по убыванию удельной стоимости, пока не кончится место в рюкзаке»)?

Какой класс ошибок допускают алгоритмы решающие задачи из класса BPP?

Является ли конкатенация двух разрешимых языков перечислимой?

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

Выберите общепринятое определение класса NPC (NP-полных задач).

тогда и только тогда, когда:

Метод многократного запуска вероятностного алгоритма, с целью уменьшения вероятности ошибки называется:

Какова точность, гарантируемая жадным алгоритмом в задаче о покрытии?

Какой алгоритм используется в алгоритме Кристофидеса?