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

1

2

3

4

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

Вариант 658895803.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

Пусть

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

Что верно?

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

Вопрос 3

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

Нет;
Да;

Вопрос 4

Пусть сводится по Карпу к . Выберите верное утверждение:

Если , то ;
Если , то ;
Если , то ;

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

Вопрос 8

Задача 2SAT:

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

Вопрос 9

Выберите верное следствие:

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

Вопрос 10

Пусть S — задача из NPC, а Q и R — тоже задачи, но про них известно только, что Q — полиномиально сводиться по Карпу к S, а S — к R.

Что будет верно?

Q — NP-полная
Q — NP-трудная
R — NP-полная
R — NP-трудная