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

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

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

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

[ Хронологический вид ]Комментарии

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


Пусть алгоритм A присваивает всем переменным значение 1. Тогда вероятность что скобка принимает значение 1, равна 7/8(благоприятные исходы, значения литералов 001, 010, 011, 100, 101, 110, 111; не благоприятный исход 000). Пусть в КНФ m скобок, тогда

Т.е. вероятностный приближенный алгоритм гарантирует точность 7/8

Войдите, чтобы комментировать.