On Bellman’s and Knuth’s Problems and their Generalizations

Abstract

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 power 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.