05.12.2017 Нижняя оценка на доказательство формулы в системе OBDD(and, reordering) (Марсель Матдинов)

Название: Нижняя оценка на доказательство формулы в системе OBDD(and, reordering)

Время: 5 декабря, 16:30

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

Докладчик: Марсель Матдинов

Описание:

Будет доказано, что любое доказательство формулы PHP(n, l*n) в системе OBDD(and, reordering), где l - некоторая константа, большая единицы, имеет экспоненциальный от n размер. Текст доказательства в приложении.

AttachmentSize
PDF icon Pigeon.pdf201.77 KB