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

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

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

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

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

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

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

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

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

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

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

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

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