Вариант 3549338977.
Паросочетание, это подмножество...
Пусть задача A — «есть ли цикл в ненаправленном графе». Рассмотрим набор утверждений.
Что верно?
Какова точность, гарантируемая жадным алгоритмом в задаче о покрытии?
Задачи 3SAT и 2SAT:
Рассмотрим модификацию задачи «Сумма размеров», разрешим даже отрицательные размеры.
Формально: Даны натуральные числа , , и число B.
Надо узнать, существует ли решение в 0/1 переменных уравнения .
Существует ли полиномиальный алгоритм для этой задачи?