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

1

2

3

4

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

Вариант 2742935666.

Ваше имя*:

Вопрос 1

Пересечение двух каких классов окажется пустым, если окажется, что ?

и ;
и ;
и ;

Вопрос 2

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

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

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

Вопрос 3

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

Да;
Нет;

Вопрос 4

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

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

Вопрос 5

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

Вопрос 6

Пусть

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

Что верно?

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

Вопрос 7

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

Нет;
Да;

Вопрос 8

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

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

Вопрос 9

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

Вопрос 10

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

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