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

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

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

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

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

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

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

Пусть

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

Что верно?

Задачи 3SAT и 2SAT:

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

Является ли пустое множество разрешимым?

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