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

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

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

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

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

Пусть

• — задача поиска гамильтонового цикла в графе , где V — делится на 3.
• — задача подтверждения наличия гамильтонового цикла в таком графе.

Что верно?

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

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

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

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

Пусть X — задача из NP. Что верно?