Изменения

# Покажите, что в определении PRAS можно заменить константу $3/4$ в требовании, что вероятность попасть в интервал $[1-\varepsilon;1+\varepsilon]$ должна быть $3/4$, на любое другое число, строго большее $1/2$.

# Можно ли в предыдущем задании заменить $1/2$ на $0$?

# Рассмотрим формулу в ДНФ. Обозначим как $t$ количество пар $($терм$,$ удовлетворяющее этот терм назначение переменных$)$. Выберем случайно терм, где вероятность выбрать терм пропорциональна числу удовлетворяющих этот терм назначений. Выберем случайное назначение $a$, удовлетворяющее этот терм. Рассмотрим случайную величину $X = t/cov(a)$, где $cov(a)$ - число термов, удовлетворенных назначением $a$. Докажите, что $EX = Y$, где $Y$ - число удовлетворяющих назначений заданной формулы.

# На базе предыдущего задания предложите альтернативный алгоритм апроксимации числа удовлетворяющих назначений ДНФ.

# Рандомизированный алгоритм для 2SAT. Рассмотрим следующий алгоритм решения задачи удовлетворимости булевой формулы в 2КНФ с $n$ переменными. Выберем случайное значение каждой переменной. Если формула не удовлетворена, выберем случайный не удовлетворенный клоз и инвертируем значение случайной переменной в нем. Докажите, что если удовлетворяющее назначение существует, оно будет найдено за $O(n^2)$ шагов. Указание: зафиксируйте любое удовлетворяющее формулу назначение и рассмотрите задачу как случайное блуждание по прямой, где координата - это число переменных, значение которых совпадает с значением в выбранном назначении.

# Почему алгоритм из предыдущего задания не работает для 3SAT?

# Почему алгоритм из предыдущего задания не работает для поиска раскраски графа в три цвета?