MAX-SAT: вероятностное округление/Задачи/MAX-3ESAT — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
|||
| Строка 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> | ||
Версия 12:29, 31 октября 2014
Рассмотрим задачу «MAX-3ESAT», это «MAX-SAT», только в КНФ в каждой скобке ровно три литерала.
Предложите вероятностный алгоритм с точностью .
Стенин Сергей группа 974