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

1

2

3

4

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

Вариант 426506499.

Ваше имя*:

Вопрос 1

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

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

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

Вопрос 2

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

Вопрос 3

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

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

Вопрос 4

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

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

Что верно?

Вопрос 5

Задача 2SAT:

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

Вопрос 6

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

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

Вопрос 7

Выберите верное верное утверждение из списка ниже, если верных вариантов ответа несколько, то выберите наиболее сильный из них:

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

Вопрос 8

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

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

Вопрос 9

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

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

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

Вопрос 10

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

Нет;
Да;