|
ИСТИНА |
Войти в систему Регистрация |
Интеллектуальная Система Тематического Исследования НАукометрических данных |
||
Comparing the Computational Complexity of Monomials and Elements of Finite Abelian Groupsстатья
- Автор: Kochergin V.V.
- Журнал: Moscow University Mathematics Bulletin
- Том: 77
- Номер: 3
- Год издания: 2022
- Издательство: Allerton Press Inc.
- Местоположение издательства: United States
- Первая страница: 113
- Последняя страница: 119
- DOI: 10.3103/S0027132222030068
- Аннотация: 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 \times \langle a_q \rangle_{u_q}$ (it is supposed that $k_i<u_i$ for all $i$) computation and the complexityof the term $x_1^{k_1} x_2^{k_2} \ldots x_q^{k_q}$ computation are compared in the paper. We define the complexity of the computation as the minimal number of the multiplication operations, at this all the results of the 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 relation of the values above asymptotically grow as $\log_2 /( \log_2 \log_2 n)$ and$\sqrt{\log_2} / (2 \log_2 \log_2 n)$, respectively, when $n\to \infty$.
- Добавил в систему: Кочергин Вадим Васильевич