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

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

Пусть

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

Что верно?

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

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

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

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

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

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

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

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

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