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

Ссылки сюда (15) →

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

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

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

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

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

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

— Девицкий Иван 375 • 13 мая 2016 в 19:16

• страница

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