MAX-SAT: вероятностное округление/Задачи/eupce-6-1-a — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «{{проверено|}} <!-- Probability and Computing --> Рассмотрим K-ESAT, SAT, когда в каждой скобке ровно k литерало…») |
(нет различий)
|
Текущая версия на 15:05, 18 мая 2023
Рассмотрим K-ESAT, SAT, когда в каждой скобке ровно k литералов.
Предложите Лас-Вегас алгоритм выполняющий минимум скобок, и проанализируйте матожидание его времени выполнения.