ИСТИНА

С точки зрения сложности вычислений рассматриваются различные обобщения задачи о возведении в степень: задача Д.Кнута о вычислении набора степеней одной переменной, задача Р.Беллмана о вычислении одночлена общего вида, задача О.Б.Лупанова о вычислении элементов конечной абелевой группы по ее образующим, задача Н.Пиппенджера о вычислении систем одночленов. В качестве вычислительных моделей помимо классических схем из умножений рассматриваются схемы из умножений и делений, схемы из делений, схемы из умножений, допускающие использование величин, обратных к переменным, а также схемы композиции. Дается обзор как известных, так и новых результатов.