УДК 519.71

О сложности вычисления некоторых систем одночленов схемами композиции / Е. Н. Трусевич. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2014. № 5. С. 18-22.

Исследуется задача о сложности вычисления системы одночленов схемами композиции. Под сложностью в такой модели понимается минимальное число операций композиции, достаточное для вычисления системы по переменным. Установлено, что рассматриваемая мера сложности может быть значительно меньше известных мер сложности, соответствующих моделям, допускающим, например, либо только операцию умножения, либо операции умножения и деления, либо операцию умножения с возможностью использования величин, обратных к переменным. Однако это свидетельство значительной "вычислительной силы" изучаемой модели не носит универсальный характер, что подтверждено соответствующим примером. Кроме того, для системы, состоящей из двух одночленов от двух переменных, получено точное значение сложности. Также установлено, что при вычислениях с использованием операции композиции не работают (или работают в недостаточной мере) соображения двойственности.

Ключевые слова: система мономов, схема композиции, схема из функциональных элементов, сложность схемы.

Библиогр. 10.