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

Материал из DISCOPAL
< MAX-SAT: вероятностное округление‎ | Задачи
Версия от 15:49, 20 мая 2020; StasFomin (обсуждение | вклад) (Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]])

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

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

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

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


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

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

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