Что: | Лекция |
Когда: | Воскресенье, 30 октября 2011, 13:00–14:35 |
Где: | ПОМИ РАН |
Слайды: | boolean_functions_complexity_lecture_301011.pdf |
Связь глубины и размера формулы: \( D(f) = \Theta (\log L(f)) \) . Нижняя оценка \( n^2 \) на формульную сложность универсальной функции. Метод случайных подстановок Субботовской, нижняя оценка \( n^{1.5} \) для формул де Моргана для функции четности. Функция Андреева, нижняя оценка \( n^{2.5} \) для формул де Моргана.