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

Аннотация

Получены асимптотически точные оценки сложности вычисления классов (m,n)(m,n)-матриц с коэффициентами из множества 0,1,…,q−10,1,…,q−1 вентильными схемами ограниченной глубины dd при некоторых соотношениях между mm, nn и qq. В наиболее важном случае q=2q=2 показано, что асимптотика сложности класса булевых (m,n)(m,n)-матриц log n=o(m)n=o(m), log m=o(n)m=o(n), достигается на схемах глубины 3.
Ил. 1, библиогр. 11.