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.