Сложность умножения в некоторых групповых алгебрах

В данной работе представлены некоторые результаты из сравнительно новой области теории сложности алгоритмов – алгебраической теории сложности. Рассматривается сложность умножения (билинейная сложность) в групповых алгебрах. В 6-мерной групповой алгебре ${\mathbf C}(S_3)$ над полем комплексных чисел, базисом которой являются подстановки третьего порядка, найден билинейный алгоритм для умножения с мультипликативной сложностью 9 (вместо тривиальных 36) и доказано, что эта оценка неулучшаема. Доказан ряд утверждений о структуре групповой алгебры ${\mathbf C}(S_3)$, в частности, показано, что алгебра ${\mathbf C}(S_3)$ разлагается в прямое произведение алгебры матриц второго порядка и двух одномерных алгебр.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 03–01–00783.