MAX-SAT: вероятностное округление/Задачи/MAX-3ESAT — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 3: Строка 3:
 
Предложите вероятностный алгоритм с точностью <m>\frac{7}{8}</m>.
 
Предложите вероятностный алгоритм с точностью <m>\frac{7}{8}</m>.
  
−
[[Category:На проверку]]
+
[[Category:Решенные задачи]]
−
 
+
−
== Стенин Сергей группа 974 ==
+
−
 
+
−
<m>
+
−
 
+
−
Пусть $n_1$ --- ответ алгоритма "каждая переменная в 0 с вероятностью $1/2$ и в 1 с вероятностью $1/2$" на входе с числом скобок $m$.
+
−
 
+
−
Тогда $$E n_1\geq \frac78m$$
+
−
Покажем это. Для скобки $C$ вероятность $P(C = 0) = \frac18$, $P(C = 1) = \frac78$, поэтому для скобки $C_i,$ зависящей от трех литералов $E C_i(x) = \frac78$. Поэтому для формулы, состоящей из скобок $C_1,\dots,C_m$ будет выполнено
+
−
$$
+
−
E\sum_i C_i(x) = \frac78m
+
−
$$
+
−
То есть предлагаемый вероятностный алгоритм дает точность не менее $\frac78$
+
−
 
+
−
</m>
+

Версия 09:43, 24 декабря 2014

Рассмотрим задачу «MAX-3ESAT», это «MAX-SAT», только в КНФ в каждой скобке ровно три литерала.

Предложите вероятностный алгоритм с точностью .

Источник — «https://discopal.ispras.ru/index.php?title=MAX-SAT:_вероятностное_округление/Задачи/MAX-3ESAT&oldid=3265»