On the Computation Complexity of the Systems of Finite Abelian Group Elementsстатья
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 15 февраля 2024 г.
Аннотация:The computation complexity of the systems of the finite Abelian group elements isstudied in the paper. The complexity of computation means the minimal number of group operationsrequired to calculate elements of the system over the basis elements, all results of intermediatecalculations may be used multiple times. We define the Shannon function L(n, m) as the maximalcomplexity of m-elements system group, the maximum i s taken over all Abelian groups of orderless than n, over all their bases, over all computed systems. It is stated that, if m = o(log log n)for n →∞, then the asymptotic equality L(n, m) ∼ log2n is valid. In addition, the asymptoticsof the maximal possible difference of computation complexity of the systems of finite Abelian groupelements and the computation complexity of a monomial system corresponding to the representationof these elements over basis elements is obtained under the same conditions.