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

• Автор: Поспелов, Алексей Дмитриевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Москва
• Количество страниц: 102 с. : ил.

Оглавление
Введение
1 Оценки умножения в групповых алгебрах
1.1 Основные понятия
1.2 Модель вычислений
1.3 Используемые методы
2 Коммутативные групповые алгебры
2.1 Групповые алгебры над алгебраически замкнутыми полями
2.2 Определитель циклической матрицы над
алгебраически замкнутым полем
2.3 Ранг умножения в групповых алгебрах
циклических групп
2.4 Ранг умножения в групповых алгебрах произвольных абелевых групп
3 Алгебры над вещественным полем
3.1 Ранг умножения в групповых алгебрах циклических групп
над полем вещественных чисел
3.2 Ранг умножения в групповых алгебрах произвольных абелевых групп над полем вещественных чисел

Введение
Алгоритмическое решение задач всегда было одним из основных предметов математики. В течение долгого времени такие решения были основаны на интуитивных соображениях, и только в XX веке ряд метаматематических проблем привел к интенсивному поиску точной математической формализации понятий вычислимости и алгоритма.
В 1930-х годах был предложен ряд формализаций понятий алгоритма. Наиболее известные из них — машина Тьюринга, нормальный алгоритм Маркова, рекурсивные функции, машина Поста и другие. Все эти формализации алгоритма оказались эквивалентными с точки зрения алгоритмической разрешимости проблем. Последнее было обобщено в известном тезисе Чёрча о том, что формальное определение алгоритма эквивалентно его интуитивному пониманию. В первую очередь эти понятия помогли установить алгоритмическую неразрешимость некоторых проблем, таких как, например, проблема останова, проблема пустоты и десятая проблема Гильберта. Во-вторых, такие модели, как машина Тьюринга и рекурсивные функции, оказали влияние на возникновение и развитие языков программирования.
С развитием компьютеров большую важность приобрел вопрос эффективности вычислений. В то время как для ряда практически важных и теоретически интересных проблем удалось найти эффективные

ВВЕДЕНИЕ

решающие алгоритмы, некоторые задачи оказались достаточно трудны и быстрые алгоритмы для них до сих пор неизвестны. Это привело к возникновению и развитию теории слооюности, занимающейся оценками количества ресурсов, необходимых алгоритму для решения задачи, таких как число шагов в той или иной модели вычислений (затрачиваемое время) или используемой в алгоритме памяти.
Данная работа выполнена в контексте алгебраической теории сложности — теории сложности алгебраических задач в алгебраической модели вычислений. Примерами алгебраических задач являются операции над многочленами, например, вычисление многочлена в заданной точке, умножение и деление многочленов, матричные вычисления, такие как умножение матриц, обращение, вычисление характеристического многочлена, решение систем линейных алгебраических уравнений, нахождение наибольшего общего делителя двух натуральных чисел, и многие другие. Алгебраическая модель вычислений, как правило, подразумевает некоторую пошаговую процедуру, вычисляющую на каждом шаге определенную алгебраическую величину как функцию от входных значений и уже вычисленных величин. Вычисление считается законченным, если все требуемые величины вычислены на каких-то шагах процедуры. Первым приближением понятия сложности алгебраической проблемы является минимальное количество таких шагов, необходимое для вычисления всех требуемых величин. Примерами алгебраических алгоритмов являются схема Горнера вычисления значения многочлена в точке, алгоритм Карацубы умножения чисел, алгоритм Штрассена умножения матриц и многие другие.
Одной из центральных задач алгебраической теории сложности является сложность умножения в алгебрах. Для этого сначала определяется
ГЛАВА 2. КОММУТАТИВНЫЕ ГРУППОВЫЕ АЛГЕБРЫ
(а) к {, £ $ Ь. В этом случае сумма (2.7) приобретает вид
А—/ п — к I
акС :
к / / .
'д — Ъ + к
д — к] д —
к=Ь—£
Обозначим 11 = к — £ 4- £ Тогда, согласно (2.4) и (2.6),
кд-1,—с

так как &+£ — 4р — 41, & + £ — £д, вто время как 2д — £ + 1 2д — д + 1 = р, 2д — £+1<2д+1 = 2р — 1.
Таким образом, при к+£ < р+£, к, £ t выполняется сГке = 0.
(Ь) к £, £ > 4. В этом случае сумма (2.7) приобретает вид

ч-Е(;:ЭС;1Г
Обозначим р = к — к. Тогда

аы :

д-к + р//д + к-1~р р. / £ + &
Если £<р<&+£— <, то1р<д, д — & + р > р, д — к + /л д + i — 4 2д < 2р — 1. Следовательно, при к<цк + £ — £, согласно (2.6) и (2.4),
“Ь-еС-ПСг.'гЭ--.1)
аналогично предыдущему случаю.
Таким образом, при & + £ < р + £, А: £ > £ выполняется
<4 = 0.
(с) к > £, £ £. В силу симметрии формулы (2.7) относительно (к, &) *-+ (А, £), этот случай аналогичен предыдущему разобранному случаю.