Алгоритмическая сложность некоторых линейных неассоциативных алгебр

Аннотация

Одной из центральных задач алгебраической теории сложности является сложность умножения в алгебрах. Для этого сначала определяется понятие алгебры и фиксируется класс изучаемых алгебр. Затем уточняется понятие алгоритма и его сложности.
В наиболее общем смысле алгеброй называется множество с операциями. Операция определяется, как правило, как функция одного или нескольких элементов множества, множеством значений которой является исходное множество или некоторое его подмножество. Обычно фиксируется некоторое множество элементарных операций, например, булева операция над двумя битами, сложение или умножение двух чисел, после чего фиксируется модель вычислений, например, последовательный алгоритм, на каждом из шагов которого выполняется одна элементарная операция над некоторыми входами и результатами промежуточных вычислений, результат которой может быть использован для входа элементарной операции на последующих шагах алгоритма.
К наиболее значимым следует отнести алгоритм умножения чисел "в столбик", имеющий квадратичную сложность (по длине входа) и алгоритм умножения матриц "строка на столбец", имеющий сложность $O(mnp)$ для умножения матриц размера $m\times n$ на $n \times p$.
Оценка сложности алгебр из других более сложных классов актуальна. В данной статье мы выводим оценку сложности невырожденной симметрической билинейной формы над алгебраическим замкнутым полем для простой йордановой алгебры, а также оценку для тела Кэли-Диксона и простой алгебры Ли над характеристическим полем.