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