Вариант 1119274874.
Какие условия на существование полиномиального в среднем алгоритма упаковки требуются в соответствующей теме?
В теме о полиномиальном в среднем алгоритме для задачи о рюкзаке полиномиальность в среднем доказана для следующего распределения входных данных:
Цикл, проходящий через все ребра графа по одному разу, называется
В теме про полиномиальный в среднем алгоритм для «SAT» мы применяли формулу…
Задача Коммивояжера, в которой для матрицы расстояний выполнено неравенство треугольника, называется:
Паросочетание, это подмножество...
Гамильтонов цикл в графе:
Есть граф G=(V,E). Разбиение множества вершин V на непересекающиеся множества S и T называется:
Какой класс ошибок допускают алгоритмы решающие задачи из класса PP?
Какой класс ошибок допускают алгоритмы решающие задачи из класса ZPP?