Laboratory of Mathematical Logic at PDMI

Вторник, 12 октября, комната 106. Начало в 18:00.

12 октября.
Э.Гирш. Доклад о новых результатах о выполнимости (независимый, но непересекающийся с докладом в понедельник).
Точный круг вопросов будет определен по результатам обсуждения доклада в понедельник, но во всяком случае в доклад войдут результаты, касающиеся "фазового перехода" для выполнимости. Кратко, тематика такова: для 2-выполнимости известно, что если в формуле соотношение кол-ва дизъюнкций и переменных < 1, то формула почти наверняка выполнима, а если > 1, то почти наверняка невыполнима. Уже для 3-выполнимости точная оценка неизвестна, из компьютерных экспериментов предполагается, что граничное соотношение должно быть около 4.25. Будут рассказаны какие-либо из оценок этого соотношения сверху и/или снизу (в преддверии надвигающегося доклада Д.В.Карпова о похожем результате для 3-раскрашиваемости.)