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

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

Вариант 1315867478.

Ваше имя*:

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

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

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

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

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

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

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

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

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

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

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

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

Возможно ли сконструировать алгоритм , который для произвольной машины Тюринга и входа определит, остановится ли данная М.Т. на заданном входе?

Нет
Формально да, но никто не знает как именно это сделать (примерно как со вполне упорядочиванием );
Да, известно чёткое описание того, как это делать;