Теоретический семинар (осень 2017)

Название: Системы доказательств, основанные на OBDD

Время: 21 ноября, 16:30

Место: ПОМИ РАН, ауд. 402

Докладчик: Елизавета Адекова

Описание:

На семинаре мы рассмотрим системы доказательств, основанные на OBDD: OBDD(and) и OBDD(and, reordering). Мы изучим простые свойства этих систем и докажем, что OBDD(and, reordering) сильнее, чем OBDD(and), построив семейство формул, не имеющих короткого доказательства в OBDD(and), но имеющих полиномиальное доказательство в OBDD(and, reordering).

 

 

Время: 24 октября, 16:30

Место: ПОМИ РАН, ауд. 402

Докладчик: Данил Сагунов

Описание:

Мы рассмотрим основные понятия параметризованной сложности: 

параметризованная задача - задача, экземпляры которой расширены дополнительным числом-параметром;

класс FPT - класс параметризованных задач, для которых для любого фиксированного значения параметра существует алгоритм, работающий полиномиальное время;

Время: 3 октября, 16:30
Место: ПОМИ РАН, аудитория 402
Докладчик: Грязнов Святослав

Описание 

Доклад по статье Dmitry Itsykson and Dmitry Sokolov, Lower bounds for splittings by linear combinations.

Время: 26 сентября, 16:30
Место: ПОМИ РАН, аудитория 402
Докладчик: Воронова Надежда

Описание:

Продолжение предыдущего доклада.
В этот раз будут рассмотрены:

  •  алгоритмы для нахождения хроматического числа графа
  •  алгоритм для проверки графа на 3-раскрашиваемость
  •  сведения разных задач, связанных с раскрасками, друг к другу, и

доказательство NP-полноты задачи о раскраске.

Время: 12 сентября, 16:30
Место: ПОМИ РАН, аудитория 402
Докладчик: Воронова Надежда

Описание:

Будут рассмотрены основные задачи, связанные с раскраской графов и
алгоритмы для них: