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

1

2

3

4

Еженедельный по «сложности алгоритмов» для 3 курса ИСПРАН

Вариант 877248722.

Ваше имя*:

Вопрос 1

У языков L1-L4 доказаны следующие полиномиальные сводимости по Карпу: «L1→L2», «L3→L2→L4» Рассмотрим утверждения:

I: Если L4 в P, то L2 в P
II: Если L1 или L3 в P, то L2 в P
III: L1 в P, тогда и только тогда, когда L3 в P
IV: Если L4 в P, то L1 в P и L3 в P.

Вопрос 2

Вопрос 3

Для какой задачи не существует (при условии ) полиномиального алгоритма:

Аппроксимация Рюкзака (Knapsack) с точностью 0.017
Аппроксимация Рюкзака (Knapsack) с точностью 0.9
Кратчайшие пути в графе
Аппроксимация MAX-SAT с точностью 0.9
Поиск эйлерова цикла в графе

Вопрос 4

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

Да
Нет

Вопрос 5

Является ли пустое множество разрешимым?

Нет;
Да;

Вопрос 6

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

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

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

Вопрос 7

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

Вопрос 8

Что верно для NP-полных и NP-трудных задач:

Первой задачей с доказанной NP-полнотой была CircuitSAT, «the circuit satisfiability problem»
Если мы хотим доказать, что задача X — NP-трудна, мы берем известную NP-полную задачу Y и сводим ее полиномиально по Карпу к X.
Ничего не верно.
Все варианты, кроме «ничего не верно»

Вопрос 9

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

Верного ответа нет
Из сводимости по Куку следует сводимость по Карпу
Из сводимости по Карпу следует сводимость по Куку

Вопрос 10

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

Обе в P
Первая неразрешима и вторая — NP-полна.
Все остальные варианты — неверны.
Первая NP-полна и вторая в P.
Обе NP-полны