On some measures of complexity of finite Abelian groups

V. V. Kochergin

Diskretnaya Matematika, Tome 27 (2015) no. 3, pp. 25-43.

Résumé

Let a finite Abelian multiplicative group $G$ be specified by the basis $B = \{ a_1, a_2, \ldots , a_q\}$, that is, the group $G$ is decomposed into a direct product of cyclic subgroups generated by the elements of the set $B$: $G= \langle a_1 \rangle \times \langle a_2 \rangle \times \ldots \times \langle a_q \rangle$. The complexity $L(g;B)$ of an element $g$ of the group $G$ in the basis $B$ is defined as the minimum number of multiplication operations required to compute the element $g$ given the basis $B$ (it is allowed to use the results of intermediate computations many times). Let $L(G, B)= \max\limits_{g \in G} L(g; B),$ $ LM(G)= \max\limits_{B} L(G, B),$ $Lm(G)= \min\limits_{B} L(G, B),$ $M(n) = \max\limits_{G \colon |G| \le n} LM(G),$ $m(n) = \max\limits_{G \colon |G| \le n} Lm(G),$ $M_{\hbox{\small av}}(n) = \left( \sum\limits_{G \colon |G|= n}{ LM(G)}\right)/{A(n)},$ $m_{\hbox{\small av}}(n) = \left( \sum\limits_{G \colon |G|= n}{ Lm(G)}\right)/{A(n)},$ where $A(n)$ is the number of Abelian groups of order $n$. In this work the asymptotic estimates for the quantities $L(G, B)$, $M(n)$, $m(n)$, $M_{\hbox{\small av}}(n)$, and ${m_{\hbox{\small av}}}(n)$ are established.

Détail

Keywords: finite Abelian group, computational complexity, addition chains, vectorial addition chains, Bellman's problem, Knuth's problem.

Bibliographie

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

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

[3] Knut D. E., Iskusstvo programmirovaniya dlya EVM, v. 2, Mir, Moskva, 1977

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

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

[6] Kochergin V. V., “O slozhnosti vychislenii v konechnykh abelevykh, nilpotentnykh i razreshimykh gruppakh”, Diskretnaya matematika, 5:1 (1993), 91–111 | MR | Zbl

[7] Kochergin V. V., “O vychislenii naborov stepenei”, Diskretnaya matematika, 6:2 (1994), 129–137 | MR | Zbl

[8] Kochergin V. V., “O slozhnosti vychislenii odnochlenov i naborov stepenei”, Diskretnyi analiz, Tr./RAN. Sib. otdelenie. In-t matematiki, 27, Izdatelstvo Instituta matematiki SO RAN, Novosibirsk, 1994, 94–107 | MR

[9] Kochergin V. V., “O slozhnosti vychislenii v konechnykh nilpotentnykh gruppakh”, Diskretnyi analiz i issledovanie operatsii, 3:1 (1996), 43–51 | MR | Zbl

[10] Kochergin V. V., “Nekotorye zadachi slozhnosti vychisleniya elementov konechnykh abelevykh grupp”, Materialy XI Mezhdunar. sem. «Diskretnaya matematika i ee prilozheniya» (Moskva, MGU, 18–23 iyunya 2012 g.), Izd-vo mekh.-mat. f-ta MGU, Moskva, 2012, 135–138

[11] Kochergin V. V., “Ob odnoi nizhnei otsenke slozhnosti vychisleniya elementov konechnykh abelevykh grupp”, Problemy teoreticheskoi kibernetiki. Materialy XVII mezhdunar. konf. (Kazan, 16–20 iyunya 2014 g.), Otechestvo, Kazan, 2014, 155–158

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

[13] Lupanov O. B., “O sinteze nekotorykh klassov upravlyayuschikh sistem”, Problemy kibernetiki, 10, Fizmatgiz, Moskva, 1963, 63–97 | MR

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

[15] Seneta E., Pravilno menyayuschiesya funktsii, Nauka, M., 1985, 144 pp. | MR

[16] Sidorenko A. F., “Slozhnost additivnykh vychislenii semeistv tselochislennykh lineinykh form”, Zap. nauchn. sem. LOMI, 105, Nauka, Leningrad, 1981, 53–61 | MR | Zbl

[17] Kholl M., Kombinatorika, Mir, Moskva, 1970 | MR

[18] Chandrasekkharan K., Vvedenie v analiticheskuyu teoriyu chisel, Mir, Moskva, 1974 | MR

[19] Endryus G., Teoriya razbienii, Nauka, Moskva, 1982 | MR

[20] Brauer A., “On addition chains”, Bull. Amer. Math. Soc., 45 (1939), 736–739 | DOI | MR

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

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

[23] Knuth D. E., Papadimitriou C. H., “Duality in addition chains”, Bull. Ass. Theor. Comput. Sci., 13 (1981), 2–4

[24] Olivos J., “On vectorial addition chains”, J. Algorithms, 2:1 (1981), 13–21 | DOI | MR | Zbl

[25] Schönhage A., “A lower bound for the lenght of addition chains”, Theor. Comput. Sci., 1 (1975), 1–12 | DOI | MR | Zbl

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