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

1

2

3

4

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

Вариант 670342992.

Ваше имя*:

Вопрос 1

Пусть X — задача из NP. Что верно?

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

Вопрос 2

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

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

Вопрос 3

Возможно ли сконструировать алгоритм , который для произвольной машины Тюринга и входа определит, остановится ли данная М.Т. на заданном входе?

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

Вопрос 4

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

Вопрос 5

У языков L1-L4 доказаны следующие полиномиальные сводимости по Карпу: «L1→L2», «L3→L2→L4» Рассмотрим утверждения:

I: Если L4 в P, то L2 в P
II: Если L1 или L3 в P, то L2 в P
III: L1 в P, тогда и только тогда, когда L3 в P
IV: Если L4 в P, то L1 в P и L3 в P.

Вопрос 6

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

Нет;
Да;

Вопрос 7

Рассмотрим две задачи разрешения, P1 и P2, такие что

P1 сводится полиномиально по Карпу к 3SAT
3SAT сводится полиномиально по Карпу к P2

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

Вопрос 8

Задача 2SAT:

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

Вопрос 9

Цикл, проходящий через все вершины графа, называется

Вопрос 10

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

и ;
и ;
и ;