Материал конференции: "XIV международный научный семинар "Дискретная математика и ее приложения" имени академика О.Б. Лупанова (20-25 июня 2022 г., Москва)"
Авторы:Кочергин В.В.
Сравнение оценок сложности для задач Р. Беллмана и О. Б. Лупанова
Аннотация:
В докладе планируется уделить внимание двум задачам. Первая из них заключается в исследовании сложности вычисления одночлена от m переменных. Эта задача сформулирована в 1963 г. Р. Беллманом и имеет интересную историю. Вторая задача, поставленная в 1988 г. О.Б. Лупановым, может быть определена как задача о сложности вычисления элемента абелевой группы. Понятно, что задачи Беллмана и Лупанова очень похожи и результаты, полученные для одной из них, как правило, переносятся на другую. Однако, в отдельных случаях значения сложности для этих задач могут и значительно отличаться. О сравнение значений сложности для задач Беллмана и Лупанова и пойдет речь в докладе.
