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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена :Решенные задачи]] на :Нерешенные задачи]])
(Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]])
(не показаны 4 промежуточные версии этого же участника)
Строка 3: Строка 3:
 
Предложите вероятностный алгоритм с точностью <m>\frac{7}{8}</m>.
 
Предложите вероятностный алгоритм с точностью <m>\frac{7}{8}</m>.
  
[[Категория:Нерешенные задачи]]
+
[[Категория:Решенные задачи]]

Версия 15:49, 20 мая 2020

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

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