Некоторые вопросы теории сложности билинейных отображений

• Автор: Лысиков, Владимир Владимирович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Москва
• Количество страниц: 73 с. : ил.

Содержание
Введение

Глава 1. Основные понятия

1.1. Билинейные отображения и алгебры

1.2. Ассоциативные алгебры над полем

1.3. Модель вычислений

1.4. Тензорные произведения и расширение кольца скаляров

Глава 2. Алгоритмы умножения обобщенных кватернионов

2.1. Алгебры обобщенных кватернионов

2.2. Билинейные отображения малого ранга

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

2.4. Ранг произведения алгебр обобщенных кватернионов .
Глава 3. Полупростые алгебры почти минимального
ранга
3.1. Следствия известных оценок
3.2. Сложность умножения в алгебрах матриц

Глава 4. Целочисленные билинейные отображения над полями различных характеристик
4.1. Ненулевые тензорные произведения
4.2. Связь между билинейными алгоритмами
4.3. Метаматематическое доказательство
Литература

Введение
Теория сложности вычислений является одной из важнейших областей математической кибернетики. После появления компьютеров измерение эффективности используемых алгоритмов и исследование возможностей их улучшения стали важными практическими вопросами, изучение которых привело, в том числе, к появлению математической теории, в рамках которой исследуется различные характеристики эффективности алгоритмов в различных математических моделях вычислений. Наиболее важные из таких характеристик — это время работы алгоритма, т. е. количество элементарных шагов в рассматриваемой модели, и используемая память. Появление теории сложности вычислений можно отнести к пятидесятым годам XX века: Б. А. Трахтеиброт в [30] утверждает, что исследования временной сложности алгоритмов в СССР начались в 1956 г., а М. Сипсер в [25] упоминает письмо К. Гёделя к Дж. фон Нейману, датируемое 1953 г. В настоящее время теория сложности вычислений является очень широкой областью исследований, включающей множество направлений и связанной практически со всеми областями математики.
Одним из направлений в теории сложности вычислений является алгебраическая теория сложности. Естественно, что алгоритмы, вычисляющие функции, связанные с какой-либо алгебраической струк-

Алгебра над F называется центральной, если ее центр совпадает с F.
Определение 2.2. Алгеброй обобщенных кватернионов над F называется простая центральная алгебра размерности 4.
Структура алгебр обобщенных кватернионов определяется следующими утверждениями:
Теорема 2.1 (см. [8]). Если char F ^ 2, то любая алгебра обобщенных кватернионов порождается двумя элементами г и j, удовлетворяющими условиям
где р, q Є F, р, q ф 0. Элементы 1, г, j, k = ij образуют базис
Теорема 2.2 (см. [8]). Если char F = 2, то любая алгебра обобщенных кватернионов порождается двумя элементами г и j, удовлетворяющими условиям
<(*+1)=р, j2 = q, ij=j(i + 1), где р, q Є F, q ^ 0. Элементы 1, і, j, к = ij образуют базис алгебры.
изоморфна алгебре матриц р2х2, либо является некоммутативной алгеброй с делением. Любая некоммутативная алгебра с делением размерности 4 является алгеброй обобщенных кватернионов.
г2 = Р, j2 = q, ij = -ji,
алгебры. Такую алгебру будем обозначать
Теорема 2.3 (см. [8]). Любая алгебра обобщенных кватернионов либо