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

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

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

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

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

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

Будет ли класс -полных задач замкнутым относительно сводимости по Карпу, если окажется, что ?

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

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

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

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

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

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