Laboratory of Mathematical Logic at PDMI

Пятница, 16 декабря, комната 106. Начало в 17:30.

Докладчик: И. Посов.

Тема: ``Фазовые переходы'' в трудных оптимизационных задачах: асимптотически точные оценки.

Abstract

Доклад по статье Dimitris Achlioptas, Assaf Naor, Yuval Peres

Будет представлен метод, позволяющий достаточно точно обнаружить расположение фазового перехода в задаче k-SAT, т.е. обнаружить границу количества клозов до которого случайная формула с большой вероятностью выполнима, а после которой с большой вероятностью невыполнима. Также будет показано, как метод можно применить для подобного вопроса в задаче Max k-SAT.