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

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

Вариант 2440753792.

Ваше имя*:

Вопрос 1

Существует ли биекция между классами и ?

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

Вопрос 2

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

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

Вопрос 3

Рассмотрим пару задач на графах.

P1
Для заданного графа, подтвердить или опровергнуть, что в нем есть цикл, которые посещает однократно все вершины, кроме первой, в которую надо вернутся, чтобы завершить цикл.
P2

Для заданного графа, подтвердить или опровергнуть, что в нем есть цикл, который проходит по каждому ребру точно один раз, без исключений.

  1.  P1 в NPC, P2 в P.
  2.  Все остальные варианты — неверны.
  3.  Обе в NPC
  4.  Обе в P
  5.  P2 в NPC, P1 в P.
  6.  X в NP, но не NP-полная.

Вопрос 4

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

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

Вопрос 5

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

  1.  Да;
  2.  Нет;

Вопрос 6

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

  1.  
  2.  
  3.  
  4.  

Вопрос 7

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

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

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

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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

  1.  Нет
  2.  Да
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-3-course-ispras-weekly»