Приближенные и вероятностые алгоритмы для булевых задач
Аннотация
Рассмотрим следующую задачу: по заданной ДНФ вычислить количество
выполняющих наборов для нее. Очевидно,
в предположении $P \ne NP$ полиномиального алгоритма не существует. Мы
представим вероятностный алгоритм,
который дает приближение к ответу с точностью не ниже $\epsilon$ с
вероятностью не ниже 3/4. При этом
сложность такого алгоритма полиномиальна по размеру формулы и $1 / \epsilon$.
Другая задача, о которой пойдет речь, такова: известна КНФ, клаузам
которой приписаны неотрицательные веса.
Требуется найти такую оценку переменных, при которой суммарный вес
всех истинных клауз становится
максимальным. Будет рассказан детерминированный полиномиальный
алгоритм, строящий оценку, вес которой
не меньше 3/4 от максимально возможного.