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