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

Материал из DISCOPAL
Перейти к: навигация, поиск

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

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