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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: добавление Категория:Теоретические задачи)
 
(не показано 13 промежуточных версий этого же участника)
Строка 3: Строка 3:
 
Предложите вероятностный алгоритм с точностью <m>\frac{7}{8}</m>.
 
Предложите вероятностный алгоритм с точностью <m>\frac{7}{8}</m>.
  
[[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>
+

Текущая версия на 06:50, 4 мая 2023

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

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