Оценки длины кода для схем из функциональных элементов

Предлагается асимптотически оптимальное кодирование схем из функциональных элементов и связанная с ним новая мера сложности схем. Для этой меры сложности получен ряд верхних и нижних оценок сложности. В том числе доказана нелинейная нижняя оценка длины кода для схемы умножения двух $n$-разрядных чисел, в то время как для сложения двух $n$-разрядных чисел эта величина является линейной по $n$.
Работа выполнена при поддержке Российского фонда фундаментальных исследований (грант № 93–011–16005), и Министерства науки и образования (грант № 93–1–60–15).