Прямая программа

В информатике неофициально прямолинейная программа представляет собой программу , которая не содержит ни одного цикла или какого-либо теста и состоит из последовательности шагов, каждая из которых применяет операцию к ранее вычисленным элементам.

Данная статья посвящена случаю, когда разрешенными операциями являются операции группы , то есть умножение и инверсия. Более конкретно, прямая программа ( SLP ) для конечной группы G = ⟨ S ⟩ — это конечная последовательность L элементов G такая, что каждый элемент L либо принадлежит S , является обратным предыдущему элементу, либо произведением двух предыдущих элементов. SLP L Говорят, что вычисляет групповой элемент g G G , если g G L , где g кодируется словом из S и обратным ему словом.

Интуитивно понятно, что SLP, вычисляющая некоторый g ∈ G, является эффективным способом хранения g как группового слова над S ; заметьте, что если g создается за i шагов, длина слова g может быть экспоненциальной по i , но длина соответствующего SLP линейна по i . Это имеет важные приложения в теории вычислительных групп , используя SLP для эффективного кодирования элементов группы в виде слов в заданном порождающем наборе.

Прямолинейные программы были представлены Бабаем и Семереди в 1984 году. как инструмент для изучения вычислительной сложности некоторых свойств группы матриц. Бабай и Семереди доказывают, что каждый элемент конечной группы G имеет SLP длины O (log ² | G |) в каждом порождающем наборе.

Эффективное решение конструктивной проблемы принадлежности имеет решающее значение для многих теоретико-групповых алгоритмов. С точки зрения SLP это можно сформулировать следующим образом. Для конечной группы G = ⟨ S ⟩ и g ∈ G найдите программу прямых, g над S. вычисляющую Проблема конструктивного членства часто изучается в контексте групп «черный ящик» . Элементы кодируются битовыми строками фиксированной длины. три оракула Для теоретико-групповых функций умножения, инверсии и проверки равенства с единицей предусмотрены . Алгоритм черного ящика — это алгоритм, который использует только эти оракулы. Следовательно, прямолинейные программы для групп «черных ящиков» представляют собой алгоритмы «черного ящика».

Явные прямолинейные программы даны для множества конечных простых групп в онлайн- атласе конечных групп .

Определение

Неформальное определение

Пусть G — конечная группа и S подмножество — ее . Последовательность L = ( g ₁ ,..., g _m ) элементов G является прямой программой над S, если каждый g _i может быть получен по одному из следующих трех правил:

1. г _я € S
2. г _я = г _j $\cdot$ g _k для некоторого j , k < i
3. г _я = г ⁻¹
   _j для некоторого j < i .

Прямая стоимость c ( g | S ) элемента g ∈ G — это длина кратчайшей прямой программы над S, вычисляющей g . Стоимость бесконечна, если g не находится в подгруппе, порожденной S .

Прямолинейная программа аналогична выводу в логике предикатов. Элементы S соответствуют аксиомам, а групповые операции соответствуют правилам вывода.

Формальное определение

Пусть G — конечная группа и S подмножество — ее . Прямая программа длины m над S, вычисляющая некоторый g ∈ G, представляет собой последовательность выражений ( w ₁ ,..., w _m ) такую, что для каждого i , wi _{является} символом некоторого элемента S , или w _i = ( w _j ,-1) для некоторых j < i , или w _i = ( w _j , w _k ) для некоторых j , k < i , таких, что w _m принимает значение g при вычислении в G в очевидном образом.

Исходное определение, представленное в требует, чтобы G =⟨ S ⟩. Представленное выше определение является общим обобщением этого понятия.

С вычислительной точки зрения формальное определение прямолинейной программы имеет некоторые преимущества. Во-первых, последовательность абстрактных выражений требует меньше памяти, чем термы в порождающем наборе. Во-вторых, это позволяет строить прямолинейные программы в одном представлении G и вычислять их в другом. Это важная особенность некоторых алгоритмов.

Примеры

Группа диэдра D ₁₂ — это группа симметрий шестиугольника. Его можно создать поворотом ρ на 60 градусов и одним отражением λ. Крайний левый столбец ниже представляет собой программу прямых линий для λρ ³ :

1. л
2. р
3. р ²
4. р ³
5. нет ³

1. λ — генератор.
2. р — генератор.
3. Второе правило: (2).(2)
4. Второе правило: (3).(2)
5. Второе правило: (1).(4)

В S6 _, группе перестановок шести букв, мы можем взять α=(1 2 3 4 5 6) и β=(1 2) в качестве образующих. Самый левый столбец здесь представляет собой пример линейной программы для вычисления (1 2 3)(4 5 6):

1. а
2. б
3. а ²
4. а ² б
5. а ² ух ты
6. а ² малыш
7. а ² баба ² малыш

1. (1 2 3 4 5 6)
2. (1 2)
3. (1 3 5)(2 4 6)
4. (1 3 5 2 4 6)
5. (1 4)(2 5 3 6)
6. (1 4 2 5 3 6)
7. (1 2 3)(4 5 6)

1. а это генератор
2. β — генератор
3. Второе правило: (1).(1)
4. Второе правило: (3).(2)
5. Второе правило: (4).(1)
6. Второе правило: (5).(2)
7. Второе правило: (6).(6)

Приложения

Краткие описания конечных групп . Прямые программы можно использовать для изучения сжатия конечных групп с помощью логики первого порядка . Они предоставляют инструмент для построения «коротких» предложений, описывающих G (т.е. намного короче, чем | G |). Более подробно, SLP используются для доказательства того, что каждая конечная простая группа имеет описание первого порядка длины O (log | G |), а каждая конечная группа G имеет описание первого порядка длины O (log ³ | Г |).

Прямые программы вычисления порождающих множеств максимальных подгрупп конечных простых групп . Онлайн-АТЛАС представлений конечных групп предоставляет абстрактные прямые программы для вычисления порождающих наборов максимальных подгрупп для многих конечных простых групп.

Пример : группа Sz(32), принадлежащая к бесконечному семейству групп Сузуки , имеет ранг 2 через генераторы a и b , где a имеет порядок 2, b имеет порядок 4, ab имеет порядок 5, ab ² имеет порядок 25 и абаб ² аб ³ имеет порядок 25. Ниже представлена ​​прямая программа, которая вычисляет порождающий набор для максимальной подгруппы E ₃₂ ·E ₃₂ ⋊C ₃₁ . Эту прямую программу можно найти в онлайн-АТЛАСЕ представлений конечных групп.

1. а
2. б
3. аб
4. Эбб
5. Эбб
6. абаббб
7. ( абб ) ¹⁸
8. ( абб ) ⁻¹⁸
9. ( абб ) ⁻¹⁸ б
10. ( абб ) ⁻¹⁸ б ( абб ) ¹⁸
11. ( оуу ) ¹⁴
12. ( оуу ) ⁻¹⁴
13. ( оуу ) ⁻¹⁴ абаббб
14. ( оуу ) ⁻¹⁴ абабб ( абабб ) ¹⁴

1. а – генератор.
2. б — генератор.
3. Второе правило: (1).(2)
4. Второе правило: (3).(2)
5. Второе правило: (3).(4)
6. Второе правило: (5).(2)
7. Второе правило повторяется: (4) умножается в 18 раз.
8. Третье правило: (7) обратное
9. Второе правило: (8).(2)
10. Второе правило: (9).(7)
11. Второе правило повторяется: (5) умножается в 14 раз.
12. Третье правило: (11) обратное
13. Второе правило: (12).(6)
14. Второе правило: (13).(11)

Теорема о достижимости

Теорема о достижимости утверждает, что для конечной группы G, порожденной S , каждый g ∈ G имеет максимальную стоимость (1 + lg| G |) ² . Это можно понимать как ограничение того, насколько сложно сгенерировать элемент группы из генераторов.

Здесь функция lg( x ) является целочисленной версией функции логарифма: для k ≥1 пусть lg( k ) = max{ r : 2 ^р ≤ k }.

Идея доказательства состоит в том, чтобы построить набор Z = { z ₁ ,..., z _s }, который будет работать как новый порождающий набор ( s будет определен в процессе). Обычно оно больше S , но любой элемент G можно выразить словом длиной не более 2| Я | над З. ​Множество Z строится путем индуктивного определения возрастающей последовательности множеств K ( i ).

Пусть K ( i ) = { z ₁ ^{1 _​} · я ₂ ^{2 _​} ·...· день _я ^{α _я} : α _j ∈ {0,1}}, где z _i — элемент группы, добавленный к Z на i -м шаге. Пусть c ( i ) обозначает длину кратчайшей прямой программы, содержащей Z ( i ) = { z ₁ ,..., z _i }. Пусть K (0) = {1 _G } и c (0)=0. Определим множество Z рекурсивно:

• Если К ( я ) ⁻¹ K ( i ) = G , объявите , что s принимает значение i и останавливается.
• В противном случае выберите какой-нибудь z _{i +1} ∈ G \ K ( i ) ⁻¹ K ( i ) (который непустой), который минимизирует «увеличение стоимости» c ( i +1) − c ( i ).

Благодаря этому процессу Z определяется таким образом, что любой g ∈ G можно записать как элемент K ( i ) ⁻¹ K ( i что эффективно упрощает генерацию из Z. ) ,

Теперь нам нужно проверить следующее утверждение, чтобы гарантировать, что процесс завершается за lg(| G |) множество шагов:

Утверждение 1. Если я < s , то | К ( я +1) | = 2| К ( я ) | .

Доказательство

Сразу видно, что | К ( я +1) | ≤ 2| К ( я ) | . Теперь предположим, что существует противоречие, что | К ( я +1) | < 2| К ( я ) | . По принципу «ячейки» существуют k ₁ , k ₂ ∈ K ( i +1) с k ₁ = z ₁ ^{1 _​} · я ₂ ^{2 _​} ·...· д _{я +1} ^{α _{я +1}} = г ₁ ^{б ₁} · я ₂ ^{б ₂} ·...· д _{я +1} ^{β _{я +1}} = k ₂ для некоторых α _j , β _j ∈ {0,1}. Пусть r — наибольшее целое число такое, что α _r ≠ β _r . Предположим, что WLOG α _r = 1. Отсюда следует, что z _r = z _p ^{− α _п} · з _{п -1} ^{− α _{п -1}} ·...· я ₁ ^{− 1 _​} · я ₁ ^{б ₁} · я ₂ ^{б ₂} ·...· z _q ^{β _q} , с p , q < r . Следовательно, z _r ∈ K ( r −1) ⁻¹ K ( r − 1), противоречие.

Следующее утверждение используется, чтобы показать, что стоимость каждого элемента группы находится в пределах требуемой границы.

Пункт 2 — c ( i ) ≤ i ² - я .

Доказательство

Поскольку c (0)=0, достаточно показать, что c ( i +1) - c ( i ) ≤ 2 i . Граф Кэли группы G связен, и если i < s , K ( i ) ⁻¹ K ( i ) ≠ G , то существует элемент вида g ₁ · g ₂ ∈ G \ K ( i ) ⁻¹ K ( я ) с г ₁ ∈ K ( я ) ⁻¹ K ( я ) и грамм ₂ ∈ S .

требуется не более 2 i шагов. Для создания g ₁ ∈ K ( i ) ⁻¹ К ( я ). Генерировать элемент максимальной длины нет смысла, так как он тождественен. Следовательно, достаточно 2 i −1 шагов. Чтобы создать g ₁ · g ₂ ∈ G \ K ( i ) ⁻¹ K ( i ), 2 i шагов достаточно.

Теперь мы закончим теорему. Поскольку К ( с ) ⁻¹ K ( s ) = G , любой g ∈ G можно записать в виде k ⁻¹
₁ · k ₂ с k ⁻¹
₁ , k ₂ ∈ K ( s ). По следствию 2 нам потребуется не более s ² − s шагов для генерации Z ( s ) = Z и не более 2 s − 1 шагов для генерации g из Z ( s ).

Следовательно, c ( g | S ) ≤ s ² + s − 1 ≤ lg ² | G | + lg| G | − 1 ≤ (1 + lg| G |) ² .