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

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

Существует ли биекция между классами и ?

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

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

Пусть

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

Что верно?

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

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

Рассмотрим пару задач на графах.

P1

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

P2

Для заданного графа, подтвердить или опровергнуть, что в нем есть цикл, который проходит по каждому ребру точно один раз, без исключений.

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

Что верно для NP-полных и NP-трудных задач: