Д. Соколов (Академический Университет)
Трудные примеры для эвристических близоруких DPLL алгоритмов.
В докладе будут рассмотрены ``близорукие'' DPLL алгоритмы с
возможностью отсечения ветвей дерева расщепления. Будет построено
семейство пар (невыполнимая формула, распределение на выполнимых
формулах) для любого количества переменных такое, что либо
математическое ожидание времени работы на невыполнимой формуле не менее
$(1 - \epsilon) 2^{n}$, где $n$ число переменных, либо вероятность
правильной работы на распределении не более $(1 - \epsilon)$.
Доклад основан на совместных результатах докладчика с Д. М. Ицыксоном.
