Laboratory of Mathematical Logic at PDMI

Пятница, 19 марта, комната 106. Начало в 19:00.

Докладчик: Д. Ицыксон.

Тема: Линейные верхние оценки времени работы алгоритма локального поиска для случайных 3-SAT с небольшим количеством дизъюнкций.

Abstract

Доклад по статье M. Alekhnovich, E. Ben-Sasson "Linear Upper Bounds for Random Walk on Small Density Random 3-CNFs"

В докладе будет дан анализ времени работы алгоритма случайного локального поиска на случайных формулах в 3-КНФ. Так же будут получены линейные оценки для формул с числом дизъюнкций, меньшим 1.63 n. Для анализа будет использоваться несложное, но мощное средство, так называемый "терминатор", взвешенный выполняющий набор. Существование небольшого "терминатора" гарантирует, что алгоритм локального поиска быстро найдет выполняющий набор.