KIAM Main page Web Library  •  Publication Searh  Русский 
Publication

Conference material: "Academician O.B. Lupanov XIV International Scientific Seminar "Discrete Mathematics and Its Applications" (20-25 June 2022, Moscow)"
Authors: Kochergin V.V.
Comparison of complexity bounds for Bellman and Lupanov problems
Abstract:
The report will focus on two issues. The first of these is to study the complexity of the calculation monomial in m variables. This problem was formulated in 1963 by R. Bellman and has an interesting history. The second problem, posed in 1988 by O.B. Lupanov, can be defined as the problem on the complexity of computing an element of an Abelian group. It is clear that the problems of Bellman and Lupanov are very similar and the results obtained for one of them, as a rule, are transferred to the other. However, in some cases, the complexity values for these tasks may differ significantly. Comparison of the complexity values for the Bellman and Lupanov problems will be discussed in the report.
Keywords:
additive chains, computing polynomials
Publication language: russian,  pages: 13 (p. 4-16)
Russian source text:
Export link to publication in format:   RIS    BibTeX
About authors:
  • Kochergin Vadim Vasilievich,  Lomonosov Moscow State University