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

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

Вариант 3027623340.

Ваше имя*:

Вопрос 1

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

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

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

Вопрос 2

Множество S является разрешимым, тогда и только тогда, когда существует такая машина Тьюринга T, что:

  1.  , то T останавливается и выводит 1, а если , то T зацикливается
  2.  , то T останавливается и выводит 1, а если , то T останавливается и выводит 0
  3.  , то T останавливается и выводит 0
  4.  , то T останавливается и выводит 1

Вопрос 3

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

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

Вопрос 4

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

  1.  Да;
  2.  Нет;

Вопрос 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.


  1.  Все остальные варианты — неверны.
  2.  Только (II)
  3.  Только (I)
  4.  Только (III)
  5.  Только (I) и (IV)

Вопрос 6

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

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

Вопрос 7

Предположим, разумеется, что Тогда что будет верно?

  1.  
  2.  
  3.  
  4.  

Вопрос 8

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

  1.  Да;
  2.  Нет;

Вопрос 9

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

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

Вопрос 10

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


  1.  Из сводимости по Карпу следует сводимость по Куку
  2.  Верного ответа нет
  3.  Из сводимости по Куку следует сводимость по Карпу
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-3-course-ispras-weekly»