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

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

Рассмотрим следующий алгоритм для задачи MAX-SAT.

• Случайно (равномерное распределение) выбираем значения переменных
• Если выполнено меньше половины скобок — повторяем.

Т.е. алгоритм гарантирует выполнение более половины скобок.

Оцените матожидание времени работы.