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

Вопрос 1

1.  Нет полиномиального алгоритма для X
2.  Если X можно решить за полиномиальное время на ДМТ, то P=NP
3.  Все остальные варианты — неверны.
4.  Если X — NP-hard, то она NP-полная
5.  X может быть неразрешима
6.  X — NP-трудная

Вопрос 2

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

Вопрос 3

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

Вопрос 4

1.  Нет
2.  Неизвестно, поскольку ответ на этот вопрос следует из истинности\ложности гипотезы Римана;
3.  Да

Вопрос 5

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

Вопрос 6

1.  Гамильтонов цикл
2.  Эйлеров цикл
3.  Цикл Нельсона
4.  Петля Нестерова
5.  Наполеонов цикл

Вопрос 7

1.  Формально да, но никто не знает как именно это сделать (примерно как со вполне упорядочиванием );
2.  Нет
3.  Да, известно чёткое описание того, как это делать;

Вопрос 8

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

Вопрос 9

1.  Нет
2.  Да

Вопрос 10

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