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