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

Версия 17:37, 20 декабря 2012

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

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