|
Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika, 2022, Number 3, Pages 6–11
(Mi vmumm4468)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
Mathematics
Comparing the computational complexity of monomials and elements of finite Abelian groups
V. V. Kochergin Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
Abstract:
The complexity of the element $a_1^{k_1} a_2^{k_2} \ldots a_q^{k_q}$ of the Abelian group $\langle a_1 \rangle_{u_1} \times \langle a_2 \rangle_{u_2} \times \ldots$\break $\ldots \times \langle a_q \rangle_{u_q}$ (it is supposed that $k_i<u_i$ for all $i$) computation and the complexity of the term $x_1^{k_1} x_2^{k_2} \ldots x_q^{k_q}$ computation are compared in the paper. The complexity of computation means the minimal possible number of multiplication operations, and all the results of intermediate multiplications can be used multiple times. It it established that if $u_1 u_2 \ldots u_q \le n$, then the maximal possible difference and ratio of the above values asymptotically grow for $n\to \infty$ as $\log_2 /( \log_2 \log_2 n)$ and $\sqrt{\log_2} / (2 \log_2 \log_2 n)$, respectively.
Key words:
finite Abelian group, computational complexity, addition chains, vectorial addition chains, Bellman's problem, Knuth's problem.
Received: 01.11.2021
Citation:
V. V. Kochergin, “Comparing the computational complexity of monomials and elements of finite Abelian groups”, Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2022, no. 3, 6–11; Moscow University Mathematics Bulletin, 77:3 (2022), 113–119
Linking options:
https://www.mathnet.ru/eng/vmumm4468 https://www.mathnet.ru/eng/vmumm/y2022/i3/p6
|
|