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

Вопрос 1

1.  Нет;
2.  Да;

Вопрос 2

1.  X — NP-трудная, но не NP-полная.
2.  Все остальные варианты — неверны.
3.  X — не NP-полная, и вообще не в NP.
4.  X — NP-полная.
5.  X в NP, но не NP-полная.

Вопрос 3

1.  Из разрешимости множества следует его перечислимость;
2.  Нет верного ответа;
3.  Перечислимые и разрешимые множества никак не пересекаются;
4.  Из перечислимости множества следует его разрешимость;

Вопрос 4

1.  Декартово произведение;
2.  Разность множеств;
3.  Дополнение;

Вопрос 5

1.  3SAT
2.  2SAT
3.  SAT
4.  TSP-выполнимость
5.  Клика (есть ли в графе клика больше заданной)
6.  Вершинное покрытие
7.  Сумма множеств

Вопрос 6

1.  Все остальные варианты — неверны.
2.  NP-полна
3.  NP-трудна, но не NP-полна.
4.  разрешима за полиномиальное время, но не за константное время.
5.  разрешима за константное время, т.к. любой вход для такой задачи выполним.

Вопрос 7

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

Вопрос 8

1.  проходит через все вершины по одному разу
2.  проходит через все ребра по одному разу
3.  проходит через все вершины и ребра по одному разу

Вопрос 9

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

Вопрос 10

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

1.  A
2.  C
3.  B
4.  Все остальные варианты — неверны.
5.  D