Теоретическая кибернетика

Рассматривается задача о сложности реализации матриц схемами композиции. Под сложностью в такой модели понимается минимальное число операций композиции, достаточное для вычисления системы по переменным. Сложность реализации матрицы интерпретируется как сложность реализации системы мономов: строки соответствуют мономам, столбцы — переменным, а элементы матрицы — степеням переменных. Используемая операция композиции является обобщением операции умножения и даёт простую и точную оценку для сложности возведения в степень. Две полученные оценки устанавливают сложность реализации матрицы размера \(2 \times q\) из целых неотрицательных чисел с точностью до константы.