RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 2022, том 34, выпуск 4, страницы 36–51 (Mi dm1708)

О сложности реализации системы из трёх мономов от двух переменных схемами композиции

С. А. Корнеев

МГУ им. М. В. Ломоносова

Аннотация: В работе исследуется сложность реализации систем мономов схемами композиции. Под сложностью в этой модели понимается минимальное количество операций, необходимое для вычисления системы мономов по переменным, при этом допускается многократное использование результатов промежуточных вычислений. Основной результат данной работы — для произвольной системы из трёх мономов от двух переменных без нулевых степеней установлена формула, выражающая сложность их совместной реализации схемами композиции с точностью до единицы.

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

УДК: 519.71

Статья поступила: 15.04.2022

DOI: 10.4213/dm1708


 Англоязычная версия: Discrete Mathematics and Applications, 2024, 34:2, 89–101


© МИАН, 2024