MAX-SAT: вероятностное округление/Задачи/eupce-6-1-a

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

Рассмотрим K-ESAT, SAT, когда в каждой скобке ровно k литералов.

Предложите Лас-Вегас алгоритм выполняющий минимум скобок, и проанализируйте матожидание его времени выполнения.

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

(нет элементов)

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