| Что: | Лекция |
| Когда: | Воскресенье, 25 сентября 2011, 13:00–14:35 |
| Где: | ПОМИ РАН |
| Слайды: | boolean_functions_complexity_lecture_250911.pdf |
Булевы функции, симметрические булевы функции. Схемы и формулы. Доказательство оценки $ \Theta(2^n/n) $ на схемную сложность почти всех булевых функций от $ n $ переменных. Лучшие текущие нижние оценки для схем и формул.
