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

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

Вариант 2419447084.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

Пусть сводится по Карпу к . Выберите верное утверждение:

  1.  Если , то ;
  2.  Если , то ;
  3.  Если , то ;

Вопрос 3

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

  1.  Вершинное покрытие
  2.  TSP-выполнимость
  3.  Сумма множеств
  4.  2SAT
  5.  3SAT
  6.  SAT
  7.  Клика (есть ли в графе клика больше заданной)

Вопрос 4

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


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

Что верно?

  1.  1 и 3
  2.  1, 2 и 3
  3.  1 и 2
  4.  Все остальные варианты — неверны.
  5.  2 и 3

Вопрос 5

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

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

Вопрос 6

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

  1.  Да
  2.  Нет

Вопрос 7

Задача 2SAT:

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

Вопрос 8

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

  1.  Нет
  2.  Да

Вопрос 9

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

  1.  
  2.  
  3.  

Вопрос 10

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

  1.  Все остальные варианты — неверны.
  2.  Если X можно решить за полиномиальное время на ДМТ, то P=NP
  3.  X — NP-трудная
  4.  Если X — NP-hard, то она NP-полная
  5.  Нет полиномиального алгоритма для X
  6.  X может быть неразрешима
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-3-course-ispras-weekly»