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