Рассматриваются следующие три задачи:

1) задача о сложности вычисления системы одночленов от нескольких переменных;

2) задача о сложности вычисления системы целочисленных линейных форм;

3) задача о сложности вычисления системы элементов свободной абелевой группы.

Эти задачи являются обобщениями задачи о наскорейшем возведении в степень, известной также как задача об аддитивных цепочках. Эти обобщения могут быть описаны на языке вычисления системы из p векторов размерности q векторными аддитивными цепочками следующим образом. Цепочка q-мерных векторов, начинающаяся с q единичных (базисных) векторов и обладающая тем свойством, что любой отличный от базисного вектор цепочки является поокоординатной суммой каких-либо двух предшествующих векторов, вычисляет систему векторов (или соответствующую ей матрицу размера p×q), если все векторы этой системы содержатся в цепочке. Сложность системы векторов (сложность матрицы) определяется как минимальная длина цепочки (число небазисных векторов), вычисляющей эту систему. Для второй задачи наряду с операцией сложения также разрешается использовать и операцию вычитания, а третья помимо базисных векторов допускает использование противоположных к ним векторов.

В докладе предполагается дать обзор известных результатов в этой области, а также представить ряд результатов автора.