Вариант 2289625016.
Существует ли биекция между классами и ?
Задачи 3SAT и 2SAT:
Является ли разрешимым множество натуральных чисел, не превосходящих :
Выберите верное утверждение
Является ли пустое множество разрешимым?
Множество S является разрешимым, тогда и только тогда, когда существует такая машина Тьюринга T, что:
Рассмотрим две задачи разрешения, P1 и P2, такие что
Что можно утверждать?
Существует ли алгоритм, который выписывает одну за другой все машины Тьюринга, которые останавливаются, будучи запущенными на пустой ленте?
Выберите верное следствие:
Пусть S — задача из NPC, а Q и R — тоже задачи, но про них известно только, что Q — полиномиально сводиться по Карпу к S, а S — к R.
Что будет верно?