Вентильные схемы ограниченной глубины

Получены асимптотически точные оценки сложности вычисления классов $(m,n)$-матриц с коэффициентами из множества $\{0,1,\dots,q-1\}$ вентильными схемами ограниченной глубины $d$ при некоторых соотношениях между $m,n$ и $q$. В наиболее важном случае $q=2$ показано, что асимптотика сложности класса булевых $(m,n)$-матриц $\log n=o(m)$, $\log m=o(n)$, достигается на схемах глубины $3$. Ил. 1, библиогр. 11.