Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 5 июня 2017 г.
Аннотация:Исследуются в асимптотической постановке различные обобщения классической задачи о наискорейшем возведении в степень,
известной также как задача об аддитивных цепочках.
Для двух наиболее известных обобщений~--- для задачи Ричарда Беллмана о сложности (наименьшем числе операций
умножения) вычисления, исходя только из переменных, нормированного одночлена от $m$ переменных и для задачи Дональда Кнута о сложности совместного вычисления
системы из $m$ степеней одной переменной~--- при слабых ограничениях предъявлено асимптотически точное решение. Кроме того, дан краткий обзор
результатов по сложности вычислений, касающихся следующих трех задач: 1) вычисление системы из $p$ нормированных одночленов от $q$ переменных;
2) аддитивные вычисления систем из $p$ линейных форм от $q$ переменных; 3) вычисление системы из $p$ элементов свободной абелевой группы с $q$ порождающими.