Вариант 1613654147.
Выберите корректное утверждение:
Существует ли алгоритм, который выписывает одну за другой все машины Тьюринга, которые не останавливаются, будучи запущенными на пустой ленте?
Задачи 3SAT и 2SAT:
Существует ли алгоритм, который выписывает одну за другой все машины Тьюринга, которые останавливаются, будучи запущенными на пустой ленте?
Выберите верное следствие:
Будет ли класс -полных задач замкнутым относительно сводимости по Карпу, если окажется, что ?
Является ли конкатенация двух разрешимых языков перечислимой?
Замкнутость по какой из операций выполнена как для разрешимых, так и для перечислимых языков?
Цикл, проходящий через все вершины графа, называется
Предположим, открыли полиномиальный алгоритм, вычисляющий наибольшую клику в заданном графе. Что тогда будет, согласно вариантам на картинке?