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

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

Выберите общепринятое определение класса NPC (NP-полных задач).

тогда и только тогда, когда:

Пусть

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

Что верно?

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

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

Гамильтонов цикл в графе:

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

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

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

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