21.11.2017 Системы доказательств, основанные на OBDD (Елизавета Адекова)

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

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

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

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

Описание:

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