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

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

Вариант 3595930027.

Ваше имя*:

Вопрос 1

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

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

  1.  Нет;
  2.  Да;

Вопрос 5

Существует ли алгоритм, который выписывает одну за другой все машины Тьюринга, которые останавливаются, будучи запущенными на пустой ленте?

  1.  Да
  2.  Нет

Вопрос 6

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

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

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


  1.  Обе в NP-hard
  2.  Обе в NP
  3.  P2 в NP, P1 в NP-hard
  4.  P1 в NP, P2 в NP-hard
  5.  Все остальные варианты — неверны.

Вопрос 7

У языков 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.  Только (I)
  3.  Только (I) и (IV)
  4.  Только (III)
  5.  Только (II)

Вопрос 8

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

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

Вопрос 9

Пусть S — задача из NPC, а Q и R — тоже задачи, но про них известно только, что Q — полиномиально сводиться по Карпу к S, а S — к R.

Что будет верно?

  1.  Q — NP-трудная
  2.  R — NP-трудная
  3.  Q — NP-полная
  4.  R — NP-полная

Вопрос 10

Выберите не NP-полную задачу

  1.  3SAT
  2.  SAT
  3.  2SAT
  4.  Сумма множеств
  5.  Клика (есть ли в графе клика больше заданной)
  6.  Вершинное покрытие
  7.  TSP-выполнимость
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-3-course-ispras-weekly»