Нижние оценки для формул (И. Близнец)
Сложность булевых функций


Что: Лекция
Когда: Воскресенье, 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} \) для формул де Моргана.

Материалы

Приложенные файлы