Improvement of the estimates of the computational complexity for monomials and sets of powers in Bellman’s and Knuth’s problemsстатья
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 19 сентября 2015 г.
Аннотация:We study two generalizations of the classical problem of fast exponentiation, namely:
Bellman’s problemon computational complexity (the minimal number ofmultiplications) based only
on the variables of a normalized monomial of m variables and Knuth’s problem on the complexity
of the simultaneous calculation of a system of m powers of one variable. Some results for these
problems are reviewed in the paper. The asymptotic complexity bounds for Bellman’s and Knuth’s
problems are improved for the cases whenmand complexity behave similarly (have the same growth
order). The 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 asymptotics for a wide range
of relations between parameters (the number of variables or the computed exponents, the maximal
power, and the product of all powers). Moreover, they guarantee the ratio of the upper and lower
bounds not exceeding 5/3 for all relations between the parameters.