Нижние оценки сложности булевых схем малой глубины в
произвольном базисе
Аннотация
Рассмотрены классы схем из функциональных элементов
ограниченной глубины
в базисе, состоящем из всех булевых функций (любого числа переменных).
В классах схем
глубины 2 и 3 получены рекордные нижние оценки сложности для
эффективно заданных
операторов, в частности, для оператора циклической свёртки.