Новые результаты
в задачах Р. Беллмана и Д. Кнута

Аннотация

В работе рассматриваются задача Беллмана о сложности (минимально возможном числе операций умножения, достаточном для вычисления) одночлена от \(m\) переменных и задача Кнута о сложности вычисления набора из \(m\) степеней одной переменной. Для любого фиксированного действительного числа \(a \ge 2\) и любой положительной функции \(\varphi (m)\), удовлетворяющей условию \(\lvert \log \varphi (m)\rvert =o(\log m)\), установлены асимптотически точные оценки соответствующих функций Шеннона, характеризующих максимально возможную сложность при ограничении показателей величиной \(A=\varphi (m)m^a\). Эти функции при \(m\to \infty\) асимптотически равны \(am\) и \((a-1)m\) соответственно.

Ключевые слова: аддитивные цепочки, векторные аддитивные цепочки, задача Беллмана, задача Кнута, схемная сложность.

BibTeX
@article{IS-Kochergin2026,
  author  = {Кочергин, Вадим Васильевич},
  title   = {{Новые результаты \\ в задачах Р. Беллмана и Д. Кнута}},
  journal = {Интеллектуальные системы. Теория и приложения},
  year    = {2026},
  volume  = {30},
  number  = {4},
  pages   = {27--45},
}
AMSBIB
\RBibitem{IS-Kochergin2026}
\by В.\,В.~Кочергин
\paper Новые результаты \\ в задачах Р. Беллмана и Д. Кнута
\jour Интеллектуальные системы. Теория и приложения
\yr 2026
\vol 30
\issue 4
\pages 27--45
Опубликовано на условиях лицензии Creative Commons Attribution 4.0 International (CC BY 4.0)

← К номеру журнала

× Issue cover