Аннотация:
Исследуется известная задача [4, разд. 4.6.3, упр. 32] о сложности вычисления наборов значений $x^{n_1},\dots,x^{n_m}$ для различных наборов показателей $(n_1,\dots,n_m)$. Пусть $l(x^{n_1},\dots,x^{n_m})$ — наименьшее число операций умножения, достаточное для вычисления набора степеней $x^{n_1},\dots$,$x^{n_m}$, а $L(n_1,\dots,n_m)=\max l(x^{k_1},\dots,x^{k_m})$, где максимум берется по всем наборам $(k_1,\dots,k_m)$, $1\le k_i\le n_i$, $i=1,\dots,m$. Доказано, что если последовательность наборов вида $\tilde n=(n_1,\dots,n_m)$ удовлетворяет условию
$$
m+\log_{2}(\max\,\{n_{1},\ldots,n_{m}\})
=o\left(\frac{\log_{2}\prod_{i=1}^mn_{i}}{\log_{2}\log_{2}\prod_{i=1}^mn_i}\right),
$$
то
$$
L(n_{1},\ldots,n_{m})\sim\frac{\log_{2}\prod_{i=1}^mn_{i}}{\log_{2}\log_{2}\prod_{i=1}^mn_{i}},
$$
причем
$$
l(x^{k_{1}},\ldots, x^{k_{m}})\sim\frac{\log_{2}\prod_{i=1}^mk_{i}}{\log_{2}\log_{2}\prod_{i=1}^mk_{i}}
$$
для почти всех наборов $(k_1,\dots,k_m)$ таких, что $1\le k_i\le n_i$, $i=1,\dots,m$.