Введение (А. Куликов)
Сложность булевых функций


Что: Лекция
Когда: Воскресенье, 25 сентября 2011, 13:00–14:35
Где: ПОМИ РАН
Слайды: boolean_functions_complexity_lecture_250911.pdf

Описание

Булевы функции, симметрические булевы функции. Схемы и формулы. Доказательство оценки \( \Theta(2^n/n) \) на схемную сложность почти всех булевых функций от \( n \) переменных. Лучшие текущие нижние оценки для схем и формул.

Материалы

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