01.12.2015 Нижняя оценка на размер OBDD для выполнимых цейтинских формул (Людмила Глинских)

Для выполнимых цейтинских формул для полного графа на n вершинах оценка на размер OBDD с любым порядком переменных — $2^{\Omega(\sqrt{n})}$. В данном докладе будет определено понятие цейтинской формулы и доказана данная оценка.