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

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

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

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

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

Пусть

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

Что верно?

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

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

P1

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

P2

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

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

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

Выберите верное следствие:

Возможно ли сконструировать алгоритм , который для произвольной машины Тюринга и входа определит, остановится ли данная М.Т. на заданном входе?

Выберите не NP-полную задачу