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

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

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

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

Пересечение двух каких классов окажется пустым, если окажется, что ?

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

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

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

Задача 2SAT:

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

I

Если L4 в P, то L2 в P

II

Если L1 или L3 в P, то L2 в P

III

L1 в P, тогда и только тогда, когда L3 в P

IV

Если L4 в P, то L1 в P и L3 в P.

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