On the computation complexity of the systems of finite Abelian group elements

V. V. Kochergin

Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 4 (2023), pp. 22-29

Résumé

The computation compelxity of the systems of the finite Abelian group elements is studied in the paper. The complexity of computation means the minimal number of group operations required to calculate elements of the system over the basis elements, all results of intermediate calculations may be used multiple times. We define the Shannon function $L(n, m)$ as the maximal complexity of $m$-elements system group, the maximum is taken over all Abelian groups of order less than $n,$ over all their bases, over all computed systems. It is stated that if $m = o(\log \log n)$ for $n \to \infty$, than the asymptotic equality $L(n,m) \sim \log_2 n$ is valid. In addition, the asymptotic of the maximal possible difference of computation complexity of the systems of a finite Abelian group elements and the computation complexity of a monomial system corresponding to the representation of these elements over basis elements is obtained under the same conditions.

Bibliographie

[1] Lupanov O.B., “O sinteze nekotorykh klassov upravlyayuschikh sistem”, Problemy kibernetiki, 10, Fizmatgiz, M., 1963, 63–97

[2] Knut D.E., Iskusstvo programmirovaniya, v. 2, 3-e izd., Izdatelskii dom “Vilyams”, M., 2000 | MR

[3] Kochergin V.V., “O slozhnosti vychislenii v konechnykh abelevykh gruppakh”, Matematicheskie voprosy kibernetiki, 4, Nauka, M., 1992, 178–217

[4] Kochergin V.V., “O nekotorykh merakh slozhnosti konechnykh abelevykh grupp”, Diskretn. matem., 27:3 (2015), 25–43 | DOI

[5] Kochergin V.V., “Zadachi Bellmana, Knuta, Lupanova, Pippendzhera i ikh variatsii kak obobscheniya zadachi ob additivnykh tsepochkakh”, Matematicheskie voprosy kibernetiki, 20, Fizmatlit, M., 2022, 119–256

[6] Glukhov M.M., Zubov A.Yu., “O dlinakh simmetricheskikh i znakoperemennykh grupp podstanovok v razlichnykh sistemakh obrazuyuschikh”, Matematicheskie voprosy kibernetiki, 8, Nauka, M., 1999, 5–32

[7] Olshanskii A.Yu., “O slozhnosti vychislenii v gruppakh”, Sorosovskii obrazovatelnyi zhurnal, 6:3 (2000), 118–123

[8] Kochergin V.V., “O slozhnosti vychislenii v konechnykh abelevykh gruppakh”, Dokl. AN SSSR, 317:2 (1991), 291–294 | Zbl

[9] Kochergin V.V., “Ob odnoi zadache O. B. Lupanova”, Mat-ly XII Mezhdunar. seminara “Diskretnaya matematika i ee prilozheniya” im. akademika O. B. Lupanova, M., 2016, 4–17 | MR

[10] Kochergin V.V., “Sravnenie slozhnosti vychisleniya odnochlenov i elementov konechnykh abelevykh grupp”, Vestn. Mosk. un-ta. Matem. Mekhan., 2022, no. 3, 6–11

[11] Kochergin V.V., “Sravnenie otsenok slozhnosti dlya zadach R. Bellmana i O. B.\;Lupanova”, Mat-ly XIV Mezhdunar. seminara “Diskretnaya matematika i ee prilozheniya” im. akademika O. B.\;Lupanova (Moskva, MGU, 20–25 iyunya 2022 g.), IPM im. M. V.\;Keldysha, M., 2022, 4–16

[12] Yao A. C.C., “On the evaluation of powers”, SIAM J. Comput, 5 (1976), 100–103 | DOI | MR | Zbl

[13] Gashkov S.B., Kochergin V.V., “Ob additivnykh tsepochkakh vektorov, ventilnykh skhemakh i slozhnosti vychisleniya stepenei”, Metody diskretnogo analiza v teorii grafov i slozhnosti, 52, Novosibirsk, 1992, 22–40 | MR | Zbl

[14] Kochergin V.V., “Utochnenie otsenok slozhnosti vychisleniya odnochlenov i naborov stepenei v zadachakh Bellmana i Knuta”, Diskretn. analiz i issled. operatsii, 21:6 (2014), 51–72 | Zbl

[15] Kochergin V.V., “O zadachakh Bellmana i Knuta i ikh obobscheniyakh”, Fund. i prikl. matem., 20:6 (2015), 159–189

[16] Straus E.G., “Addition chains of vectors”, Amer. Math. Monthly, 71 (1964), 806–808 | MR

[17] Pippenger N., “On evaluation of powers and monomials”, SIAM J. Comput., 9:2 (1980), 230–250 | DOI | MR | Zbl

[18] Jukna S., Sergeev I., “Complexity of linear Boolean operators”, Found. and Trends in Theor. Comput. Sci., 9:1 (2013), 1–123 | DOI | MR | Zbl

[19] Morgenstern J., “Note on a lower bound of the linear complexity of the fast Fourier transform”, J. Assoc. Comput. Mach., 20 (1973), 305–306 | DOI | MR | Zbl