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

Вопрос 1

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

Вопрос 2

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

Вопрос 3

1.  Да
2.  Неизвестно, поскольку ответ на этот вопрос следует из истинности\ложности гипотезы Римана;
3.  Нет

Вопрос 4

1.  
2.  ;
3.  ;

Вопрос 5

Вопрос 6

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

Вопрос 7

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

Вопрос 8

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

Вопрос 9

1.   и ;
2.   и ;
3.   и ;

Вопрос 10

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