Comparing the computational complexity of monomials and elements of finite Abelian groups

V. V. Kochergin

Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 3 (2022), pp. 6-11

Résumé

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.

Bibliographie

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

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

[3] Downey P., Leong B., Sethi R., “Computing sequences with addition chains”, SIAM J. Comput., 10 (1981), 638–646 | DOI | MR | Zbl

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

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

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

[7] Bellman R.E., “Addition chains of vectors (Advanced problem 5125)”, Amer. Math. Monthly, 70 (1963), 765 | MR

[8] Sidorenko A.F., “Slozhnost additivnykh vychislenii semeistv tselochislennykh lineinykh form”, Zap. nauch. seminarov LOMI, 105, Nauka, L., 1981, 53–61 | Zbl

[9] Knut D.E., Iskusstvo programmirovaniya dlya EVM, v. 2, 1-e izd., Mir, M., 1977 | MR

[10] 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

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

[12] Jukna S., Sergeev I., “Complexity of linear Boolean operators”, Found. and Trends in Theor. Comput. Sci., 9:1 (2013), 1–123 | 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 | Zbl

[14] Erdos P., “Remarks on number theory, III: On addition chains”, Acta Arithm., 6 (1960), 77–81 | DOI | MR | Zbl

[15] Lupanov O.B., “Ob odnom podkhode k sintezu upravlyayuschikh sistem — printsipe lokalnogo kodirovaniya”, Problemy kibernetiki, 14, Nauka, M., 1965, 31–110

[16] Kochergin V.V., “O slozhnosti vychislenii odnochlenov i naborov stepenei”, Diskretnyi analiz, Tr. In-ta matematiki SO RAN, 27 Sib. otd-e. In-t matematiki, Novosibirsk, 1994, 94–107 | MR | Zbl

[17] 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

[18] Kochergin V. V., “Ob asimptotike slozhnosti additivnykh vychislenii sistem tselochislennykh lineinykh form”, Diskretn. analiz i issled. operatsii. Ser. 1, 13:2 (2006), 38–58 | Zbl