31
правка
Изменения
typo fix
# Можно ли в предыдущем задании заменить $1/2$ на $0$?
# Можно ли в решении задания 73 брать среднее значение в качестве оценки?
# Рассмотрим формулу в ДНФ. Обозначим как $t$ количество пар $($терм$, $ удовлетворяющее этот терм назначение перемеррыхпеременных$)$. Выберем случайно терм, где вероятность выбрать терм пропорциональна числу удовлетворяющих этот терм назначений. Выберем случайное назначение $a$, удовлетворяющее этот терм. Рассмотрим случайную величину $X = t/cov(a)$, где $cov(a)$ - число термов, удовлетворенных назначением $a$. Докажите, что $EX = Y$, где $Y$ - число удовлетворяющих назначений заданной формулы.
# На базе предыдущего задания предложите альтернативный алгоритм апроксимации числа удовлетворяющих назначений ДНФ.
# Рандомизированный алгоритм для 2SAT. Рассмотрим следующий алгоритм решения задачи удовлетворимости булевой формулы в 2КНФ с $n$ переменными. Выберем случайное значение каждой переменной. Если формула не удовлетворена, выберем случайный не удовлетворенный клоз и инвертируем значение случайной переменной в нем. Докажите, что если удовлетворяющее назначение существует, оно будет найдено за $O(n^2)$ шагов. Указание: зафиксируйте любое удовлетворяющее формулу назначение и рассмотрите задачу как случайное блуждание по прямой, где координата - это число переменных, значение которых совпадает с значением в выбранном назначении.
