|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
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 г.
- Автор: Kochergin V.V.
- Журнал: Journal of Applied and Industrial Mathematics
- Том: 9
- Номер: 1
- Год издания: 2015
- Издательство: Maik Nauka/Interperiodica Publishing
- Местоположение издательства: Russian Federation
- Первая страница: 68
- Последняя страница: 82
- DOI: 10.1134/S1990478915010019
- Аннотация: 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.
- Добавил в систему: Кочергин Вадим Васильевич