Уточнение оценок сложности вычисления одночленов и наборов степеней в задачах Беллмана и Кнута

Изучаются два обобщения классической задачи о наискорейшем возведении в степень – задача Беллмана о сложности (наименьшем числе операций умножения) вычисления исходя только из переменных нормированного одночлена от $m$ переменных и задача Кнута о сложности совместного вычисления системы из $m$ степеней одной переменной. Даётся обзор некоторых результатов, связанных с этими задачами, а также уточняются асимптотические оценки сложности в задачах Беллмана и Кнута, когда поведение величины $m$ сравнимо со сложностью (они имеют одинаковый порядок роста). Помимо того, что установленные верхние и нижние оценки сложности для задач Беллмана и Кнута для почти всех наборов степеней дают асимптотику роста сложности в широком диапазоне соотношений параметров (число переменных или вычисляемых степеней, значение максимального показателя степени и произведение всех показателей степеней), они ещё гарантируют при любом соотношении параметров превышение верхней оценки над нижней асимптотически не более, чем в $5/3$ раза. Библиогр. 25.