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

1

2

3

4

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

Вариант 3383768069.

Ваше имя*:

Вопрос 1

Пусть задача A — «есть ли цикл в ненаправленном графе». Рассмотрим набор утверждений.

(1) Задача A — в P
(2) Задача A — в NP
(3) Если задача A — NP-полна, то существует НМТ, решающая A за полиномиальное время.

Что верно?

Вопрос 2

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

Нет;
Да;

Вопрос 3

Существует ли биекция между классами и ?

Да, существует;
Нет, не существует;
Ответ на этот вопрос нет, т.к. нам ничего неизвестно про равенство классов и ;

Вопрос 4

Будет ли класс -полных задач замкнутым относительно сводимости по Карпу, если окажется, что ?

Да;
Нет;

Вопрос 5

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

;
;

Вопрос 6

Гамильтонов цикл в графе:

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

Вопрос 7

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

и ;
и ;
и ;

Вопрос 8

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

Да;
Нет;

Вопрос 9

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

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

Вопрос 10

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

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