On Bellman's and Knuth's problems and their generalizations

V. V. Kochergin

Fundamentalʹnaâ i prikladnaâ matematika, Tome 20 (2015) no. 6, pp. 159-188.

Résumé

Various generalizations of the classical problem of the fastest raising to a power (or the so-called problem on addition chains) are studied in the asymptotic sense. Under weak restrictions, we demonstrate asymptotically tight solutions of the two best known generalizations, namely, Bellman's problem on the computational complexity (on the minimal number of multiplication operations) of a normed monomial of several variables and Knuth's problem on the computational complexity of a powers system of one variable. We also briefly review some results on the computational complexity for three problems, namely, the computation of $p$-element systems of normed monomials in $q$ variables, additive computations for systems of $p$ integer linear forms over $q$ variables, and the computation of $p$-element systems of the free Abelian group with $q$ generators.

Bibliographie

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

[2] Knut D. E., Iskusstvo programmirovaniya dlya EVM, v. 2, Mir, M., 1977 | MR

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

[4] Kochergin V. V., “O slozhnosti vychislenii v konechnykh abelevykh gruppakh”, Matem. vopr. kibernet., 4, 1992, 178–217 | Zbl

[5] Kochergin V. V., “Ob additivnykh vychisleniyakh sistem tselochislennykh lineinykh form”, Vestn. Mosk. un-ta. Ser. 1. Matematika, mekhanika, 1993, no. 6, 97–101 | Zbl

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

[7] Kochergin V. V., “O slozhnosti vychislenii odnochlenov i naborov stepenei”, Diskretnyi analiz, Tr. RAN. Sib. otdelenie. In-t matem., 27, Izd-vo In-ta matem. SO RAN, Novosibirsk, 1994, 94–107 | MR

[8] Kochergin V. V., “O multiplikativnoi slozhnosti dvoichnykh slov s zadannym chislom edinits”, Matem. vopr. kibernet., 8, 1999, 63–76 | Zbl

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

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

[11] Kochergin V. V., “O slozhnosti vychisleniya sistem odnochlenov ot dvukh peremennykh”, Tr. VII Mezhdunar. konf. «Diskretnye modeli v teorii upravlyayuschikh sistem» (Pokrovskoe, 4–6 marta 2006 g.), MAKS Press, M., 2006, 185–190

[12] Kochergin V. V., “O slozhnosti vychisleniya sistemy iz trekh odnochlenov ot trekh peremennykh”, Matem. vopr. kibernet., 15, 2006, 79–155

[13] Kochergin V. V., “O slozhnosti sovmestnogo vychisleniya dvukh elementov svobodnoi abelevoi gruppy”, Materialy XVI Mezhdunar. shkoly-seminara «Sintez i slozhnost upravlyayuschikh sistem» (Sankt-Peterburg, 26–30 iyunya 2006 g.), Izd-vo mekh.-mat. f-ta MGU, M., 2006, 54–59 | MR

[14] Kochergin V. V., “O maksimalnoi slozhnosti sovmestnogo vychisleniya sistem elementov svobodnoi abelevoi gruppy”, Vestn. Mosk. un-ta. Ser. 1. Matematika, mekhanika, 2007, no. 3, 14–19 | MR | Zbl

[15] Kochergin V. V., “O slozhnosti sovmestnogo vychisleniya trekh elementov svobodnoi abelevoi gruppy s dvumya obrazuyuschimi”, Diskret. analiz i issled. operatsii. Ser. 1, 15:2 (2008), 23–64 | MR | Zbl

[16] Kochergin V. V., “Ob odnom sootnoshenii dvukh mer slozhnosti vychisleniya sistem odnochlenov”, Vestn. Mosk. un-ta. Ser. 1. Matematika, mekhanika, 2009, no. 4, 8–13 | MR | Zbl

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

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

[19] Merekin Yu. V., “Nizhnyaya otsenka slozhnosti dlya skhem konkatenatsii slov”, Diskret. analiz i issled. operatsii, 3:1 (1996), 52–56 | MR | Zbl

[20] Nechiporuk E. I., “O topologicheskikh printsipakh samokorrektirovaniya”, Probl. kibernet., 1969, no. 21, 5–102 | MR | Zbl

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

[22] Sevidzh D. E., Slozhnost vychislenii, Faktorial, M., 1998

[23] Althöfer I., “Tight lower bounds on the length of word chains”, Inform. Process. Lett., 34:5 (1990), 275–276 | DOI | MR | Zbl

[24] Arnold A., Brlek S., “Optimal word chains for the Thue–Morse word”, Inform. Comput., 83:2 (1989), 140–151 | DOI | MR | Zbl

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

[26] Bernstein D. J., Pippenger's exponentiation algorithm, , 2002 http://cr.yp.to/papers/pippenger.pdf

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

[28] Dobkin D., Lipton R. J., “Addition chain methods for the evaluation of specific polynomials”, SIAM J. Comput., 9:1 (1980), 121–125 | DOI | MR | Zbl

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

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

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

[32] Goundar R. R., Shiota K., Toyonaga M., “New strategy for doubling-free short addition-subtraction chain”, Appl. Math. Inform. Sci., 2:2 (2008), 123–133 | MR | Zbl

[33] Hebb K. R., “Some results on addition chains”, Not. Amer. Math. Soc., 21 (1974), A-294

[34] Knuth D. E., Papadimitriou C. H., “Duality in addition chains”, Bull. European Assoc. Theoret. Comput. Sci., 13 (1981), 2–4

[35] Kunihiro N., Yamamoto H., “Window and extended window methods for addition chain and addition-subtraction chain”, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., E81-A:1 (1998), 72–81

[36] Morain F., Olivos J., “Speeding up the computation on an eliptic curve using addition-subtraction chains”, Inform. Théor. Appl., 24 (1990), 531–544 | DOI | MR

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

[38] Nedjah N., Mourelle L., “Minimal addition-subtraction chains using genetic algorithm”, Advances in Information Systems, Lect. Notes Comput. Sci., 2457, Springer, Berlin, 2002, 303–313 | DOI | Zbl

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

[40] Pippenger N., “The minimum number of edges in graphs with prescribed paths”, Math. Systems Theory, 12:4 (1979), 325–346 | MR | Zbl

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

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

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

[44] Strassen V., “Berechnungen in partiellen Algebren endlichen Typs”, Computing, 11 (1973), 181–196 | DOI | MR | Zbl

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

[46] Subbarao M. V., “Addition chains some results and problems”, Number Theory and Applications, NATO Adv. Sci. Inst. Ser.: Ser. C, 265, ed. R. A. Mollin, Kluwer Academic, Dordrecht, 1989, 555–574 | MR

[47] Volger H., “Some results on addition/subtraction chains”, Inform. Proc. Lett., 20 (1985), 155–160 | DOI | MR | Zbl

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