ИСТИНА

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