Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Vestnik Moskov. Univ. Ser. 1. Mat. Mekh.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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
Full-text PDF (339 kB) Citations (1)
References:
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
English version:
Moscow University Mathematics Bulletin, 2022, Volume 77, Issue 3, Pages 113–119
DOI: https://doi.org/10.3103/S0027132222030068
Bibliographic databases:
Document Type: Article
UDC: 519.71
Language: Russian
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
Citation in format AMSBIB
\Bibitem{Koc22}
\by V.~V.~Kochergin
\paper Comparing the computational complexity of monomials and elements of finite Abelian groups
\jour Vestnik Moskov. Univ. Ser.~1. Mat. Mekh.
\yr 2022
\issue 3
\pages 6--11
\mathnet{http://mi.mathnet.ru/vmumm4468}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4480995}
\zmath{https://zbmath.org/?q=an:7596803}
\transl
\jour Moscow University Mathematics Bulletin
\yr 2022
\vol 77
\issue 3
\pages 113--119
\crossref{https://doi.org/10.3103/S0027132222030068}
Linking options:
  • https://www.mathnet.ru/eng/vmumm4468
  • https://www.mathnet.ru/eng/vmumm/y2022/i3/p6
  • This publication is cited in the following 1 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024