О задачах Беллмана и Кнута и их обобщениях

Исследуются в асимптотической постановке различные обобщения классической задачи о наискорейшем возведении в степень, известной также как задача об аддитивных цепочках. Для двух наиболее известных обобщений — для задачи Ричарда Беллмана о сложности (наименьшем числе операций умножения) вычисления (исходя только из переменных) нормированного одночлена от $m$ переменных и для задачи Дональда Кнута о сложности совместного вычисления системы из $m$ степеней одной переменной — при слабых ограничениях предъявлено асимптотически точное решение. Кроме того, дан краткий обзор результатов по сложности вычислений, касающихся следующих трёх задач: вычисление системы из $p$ нормированных одночленов от $q$ переменных; аддитивные вычисления систем из $p$ линейных форм от $q$ переменных; вычисление системы из $p$ элементов свободной абелевой группы с $q$ порождающими.