Geodesic
Improvement of complexity bounds of monomials and sets of powers computations in Bellman's and Knuth's problems
Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 6, pp. 51-72.

Voir la notice de l'article provenant de la source Math-Net.Ru

Two generalizations of the classical problem of the fastest calculation of exponent are studied. Namely, Bellman's problem on computational complexity (the minimal number of multiplication operations) based on a normalized monomial of $m$ variables and Knuth's problem on complexity of simultaneous calculation of a system of $m$ powers of one variable. Some results for these problems are reviewed in the paper. Asymptotic complexity bounds for Bellman's and Knuth's problems are improved for the cases when $m$ and complexity have similar rate of growth. Upper and lower complexity bounds for almost all sets of exponents for Bellman's and Knuth's problems that are established provide the complexity growth asymptotic for a wide range of parameters (number of variables or computed exponents, the maximal power, and the product of all powers) and their correlations. Moreover, they provide upper and lower bounds ratio no more than $5/3$ for all correlations of the parameters. Bibliogr. 25.
Keywords: addition chain, evaluation of powers, evaluation of monomials, Bellman's problem, Knuth's problem. 
@article{DA_2014_21_6_a4,
     author = {V. V. Kochergin},
     title = {Improvement of complexity bounds of monomials and sets of powers computations in {Bellman's} and {Knuth's} problems},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {51--72},
     publisher = {mathdoc},
     volume = {21},
     number = {6},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2014_21_6_a4/}
}
TY  - JOUR
AU  - V. V. Kochergin
TI  - Improvement of complexity bounds of monomials and sets of powers computations in Bellman's and Knuth's problems
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2014
SP  - 51
EP  - 72
VL  - 21
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2014_21_6_a4/
LA  - ru
ID  - DA_2014_21_6_a4
ER  - 
%0 Journal Article
%A V. V. Kochergin
%T Improvement of complexity bounds of monomials and sets of powers computations in Bellman's and Knuth's problems
%J Diskretnyj analiz i issledovanie operacij
%D 2014
%P 51-72
%V 21
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2014_21_6_a4/
%G ru
%F DA_2014_21_6_a4
V. V. Kochergin. Improvement of complexity bounds of monomials and sets of powers computations in Bellman's and Knuth's problems. Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 6, pp. 51-72. http://geodesic.mathdoc.fr/item/DA_2014_21_6_a4/

[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] Knut D. E., Iskusstvo programmirovaniya dlya EVM, v. 2, Mir, M., 1977, 724 pp. | Zbl

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

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

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

[6] Kochergin V. V., “O slozhnosti vychislenii odnochlenov i naborov stepenei”, Diskretnyi analiz, Tr. RAN. Sib. otd-nie. In-t matematiki, 27, Izd-vo Instituta matematiki SO RAN, Novosibirsk, 1994, 94–107 | MR

[7] Kochergin V. V., “O dvukh obobscheniyakh zadachi ob additivnykh tsepochkakh”, Tr. IV Mezhdunar. konf. “Diskretnye modeli v teorii upravlyayuschikh sistem” (Moskva, 19–25 iyunya 2000 g.), MAKS Press, M., 2000, 55–59

[8] Kochergin V. V., “O slozhnosti vychisleniya pary odnochlenov ot dvukh peremennykh”, Diskret. matematika, 17:4 (2005), 116–142 | DOI | MR | Zbl

[9] Kochergin V. V., “O slozhnosti vychisleniya sistemy iz trekh odnochlenov ot trekh peremennykh”, Mat. voprosy kibernetiki, 15, Nauka, M., 2006, 79–155

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

[11] Lupanov O. B., “Ob odnom podkhode k sintezu upravlyayuschikh sistem – printsipe lokalnogo kodirovaniya”, Probl. kibernetiki, 14, 1965, 31–110 | MR | Zbl

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

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

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

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

[16] Erdős P., “Remarks on number theory. III: On addition chains”, Acta Arith., 6 (1960), 77–81 | MR | Zbl

[17] Gordon D. M., “A survey of fast exponentiation methods”, J. Algorithms, 27 (1998), 129–146 | DOI | MR | Zbl

[18] Knuth D. E., Papadimitriou C. H., “Duality in addition chains”, Bull. Eur. Assoc. Theor. Comput. Sci., 13 (1981), 2–4 | MR

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

[20] Pippenger N., “On evaluation of powers and related problems”, Proc. 17th Ann. IEEE Symp. Found. Comput. Sci. (Houston, TX, 25–27 Oct. 1976), 258–263 | MR

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

[22] Southard T. H., Addition chains for the first $N$ squares, Tech. Rep. CNA-84, Univ. Texas, Austin, 1974

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

[24] Subbarao M. V., “Addition chains – some results and problems”, Number Theory and Applications, NATO Adv. Sci. Inst. Ser. Ser. C, 265, Kluwer Acad. Publ. Group, 1989, 555–574 | MR

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