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

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

Вариант 4159161644.

Ваше имя*:

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

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

Цикл, проходящий через все вершины графа, называется

У языков L1-L4 доказаны следующие полиномиальные сводимости по Карпу: «L1→L2», «L3→L2→L4» Рассмотрим утверждения:

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

Является ли разрешимым множество натуральных чисел, не превосходящих :

Нет
Неизвестно, поскольку ответ на этот вопрос следует из истинности\ложности гипотезы Римана;
Да

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

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

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

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