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

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

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

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

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

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

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

Пусть S — задача из NPC, а Q и R — тоже задачи, но про них известно только, что Q — полиномиально сводиться по Карпу к S, а S — к R.

Что будет верно?

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

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

Предположим, разумеется, что Тогда что будет верно?

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