УДК 519.71

Об одном соотношении двух мер сложности вычисления систем одночленов  / В. В. Кочергин. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2009. ? 4. С. 8-13.

Для одного класса матриц, задающих показатели степеней переменных в системе одночленов, установлена нетривиальная нижняя оценка сложности — минимального числа умножений, достаточного для вычисления системы по переменным. Также приведен пример последовательности матриц (и соответственно систем одночленов), для которой возможность использования наряду с самими переменными величин, обратных к переменным, приводит к снижению сложности асимптотически в 2 раза.

Ключевые слова: аддитивная цепочка, сложность вычисления систем одночленов.

Библиогр. 17.