Аннотация:
Заметка состоит из двух независимых частей, в первой части
введено понятие $(m,c)$-системы для набора линейных форм и подучена
нижняя оценка для алгебраической сложности вычисления $(m,c)$-систем на алгебраических схемах специального вида. Во второй части
введено понятие $l$-независимости набора булевских функций и получена нижняя оценка для некоторой меры сложности схем из булевских
функций для схем, вычисляющих $l$-независимый набор, в качестве
следствия показано, что обычный алгорифм умножения матриц
или полиномов можно реализовать на схеме из булевских функций
так, что эта реализация будет оптимальна относительно выбранной
меры сложности. Библ. 5 назв.