Перегляд вихідного коду сторінки Лінійна програма

{{не плутати|Лінійне програмування|лінійним програмуванням}}
В [[Інформатика|інформатиці]] '''лінійна програма'''&nbsp;— неформально, [[Комп'ютерна програма|програма]], яка не містить жодного циклу чи будь-яких перевірок та складається з послідовності кроків, на яких кожна [[Операція (математика)|операція]] виконується над попередньо обчисленими значеннями.

У цій статті розглянуто випадок, коли дозволеними операціями є операції [[Група (математика)|групи]], тобто множення та інверсія. Конкретніше, '''лінійна програма''' ('''ЛП''') для скінченної групи <math>G = \langle S\rangle</math>&nbsp;— це скінченна послідовність <math>L</math> елементів <math>G</math>, така що кожен елемент <math>L</math> або належить <math>S</math>, є оберненим до попереднього елемента або є добутком двох попередніх елементів. Кажуть, що ЛП <math>L</math> ''обчислює'' груповий елемент <math>g \in G</math> якщо <math>g \in L</math>, де <math>g</math> закодовано словом із <math>S</math> та оберненими до нього.

Інтуїтивно зрозуміло, що лінійне обчислення деякого <math>g \in G</math>&nbsp;— ''ефективний'' спосіб збереження <math>g</math> як слова групи над <math>S</math>; зауважте, що якщо <math>g</math> побудовано за <math>i</math> кроків, довжина слова <math>g</math> може бути експоненційною за <math>i</math>, але довжина відповідної ЛП є лінійною за&nbsp;<math>i</math>. Це має важливе застосування в [[Обчислювальна теорія груп|теорії обчислювальних груп]], у вигляді використання ЛП для ефективного кодування елементів групи як слів над даною [[Породжувальна множина групи|твірною множиною]].

Лінійні програми представили 1984 року Бабай та Семереді<ref>Babai, László, and Endre Szemerédi. «On the complexity of matrix group problems I.» Foundations of Computer Science, 1984. 25th Annual Symposium on Foundations of Computer Science. IEEE, 1984</ref> як засіб для вивчення обчислювальної складності певних властивостей [[Лінійна група|матричних груп]]. Вони довели, що кожен елемент скінченної групи <math>G</math> має ЛП довжини <math>O(log^2|G|)</math> в кожній твірній множині.

Ефективне розв'язання ''конструктивної задачі належності'' має вирішальне значення для багатьох теоретико-групових алгоритмів. З погляду ЛП це можна викласти так. Дано скінченну групу <math>G = \langle S\rangle</math> і <math>g \in G</math>, потрібно знайти ЛП, що обчислює <math>g</math> над <math>S</math>. Конструктивну задачу належності часто вивчають у [[Група чорної скриньки|групі чорної скриньки]]. Елементи кодують бітовими рядками фіксованої довжини. Для теоретико-групових функцій множення, інверсії та перевірки рівності з тотожністю надаються три ''оракули''. ''Алгоритм чорної скриньки'' використовує лише ці оракули. Отже, лінійні програми для груп чорної скриньки є алгоритмами чорної скриньки.

Явні лінійні програми для багатьох скінченних простих груп подано в онлайновому ''{{Нп|АТЛАС скінченних груп|АТЛАСІ скінченних груп|en|ATLAS of Finite Groups}}'' .

== Визначення ==

=== Неформальне визначення ===
Нехай <math>G</math>&nbsp;— скінченна група і <math>S</math>&nbsp;— підмножина <math>G</math>. Послідовність <math>L = (g_1,...,g_m)</math> елементів <math>G</math> є ''лінійною програмою'' над <math>S</math>, якщо кожне <math>g_i</math> можна отримати за одним із таких трьох правил:

# <math>g_i \in S</math>
# <math>g_i = g_j \cdot g_k</math> для деяких <math>j,k < i</math>
# <math>g_i = g_j^{-1}</math> для деякого <math>j < i</math>.

Лінійна ''вартість'' <math>c ( g | S )</math> елемента <math>g \in G</math>&nbsp;— це довжина найкоротшої лінійної програми над <math>S</math>, що обчислює <math>g</math>. Вартість нескінченна, якщо <math>g</math> не входить до підгрупи, породженої <math>S</math>.

Лінійна програма схожа на виведення в [[Логіка предикатів|логіці предикатів]]. Елементи <math>S</math> відповідають [[аксіома]]м, а групові операції&nbsp;— правилам виведення.

=== Формальне визначення ===
Нехай <math>G</math>&nbsp;— скінченна група і <math>S</math>&nbsp;— підмножина <math>G</math>. ''Лінійна програма'' довжини <math>m</math> над <math>S</math>, яка обчислює деяке <math>g \in G</math>, це послідовність виразів <math>( w_1 ,..., w_m )</math>, де для кожного <math>i</math> <math>w_i</math> є символом деякого елемента <math>S</math>, або <math>w_i = ( w_j ,-1)</math> для деякого <math>j < i</math>, або <math>w_i = ( w_j, w_k )</math> для деякого <math>j, k < i</math>, така, що <math>w_m</math> набуває значення <math>g</math> при оціненні в <math>G</math> в очевидний спосіб.

Оригінальне визначення, наведене в<ref name="Seress">Ákos Seress. (2003). Permutation Group Algorithms. [Online]. Cambridge Tracts in Mathematics. (No. 152). Cambridge: Cambridge University Press.</ref>, вимагає, щоб <math>G = \langle S\rangle</math>. Наведене вище визначення є його узагальненням.

З погляду обчислень, формальне визначення лінійної програми має деякі переваги. По-перше, послідовність абстрактних виразів потребує менше пам'яті, ніж {{Прояснити|терми твірної множини|comment=terms over the generating set}}. По-друге, це дозволяє будувати лінійні програми в одному представленні <math>G</math> і обчислювати в іншому. Це важлива особливість деяких алгоритмів<ref name="Seress"/>.

== Приклади ==
[[Діедрична група]] <math>D_{12}</math> є групою симетрій шестикутника. Її можна створити поворотом ρ на 60 градусів і одним відбиттям λ. Крайній лівий стовпець наведеного нижче є лінійною програмою для λρ<sup>3</sup>:
&nbsp;{{col-begin}}
{{col-break}}
# λ
# ρ
# ρ<sup>2</sup>
# ρ<sup>3</sup>
# λρ<sup>3</sup>
{{col-break}}
# λ&nbsp;— твірна.
# ρ&nbsp;— твірна.
# Друге правило: (2).(2)
# Друге правило: (3).(2)
# Друге правило: (1).(4)
{{col-end}}
У групі перестановок із шести літер <math>S_6</math>твірними можна взяти α=(1 2 3 4 5 6) і β=(1 2). Крайній лівий стовпець тут є прикладом лінійної програми для обчислень (1 2 3)(4 5 6):{{col-begin}}
{{col-break}}
# ''a''
# ''b''
# ''ab''
# ''abb''
# ''ababb''
# ''ababbb''
# (''abb'')<sup>18</sup>
# (''abb'')<sup>−18</sup>
# (''abb'')<sup>−18</sup>''b''
# (''abb'')<sup>−18</sup>''b''(''abb'')<sup>18</sup>
# (''ababb'')<sup>14</sup>
# (''ababb'')<sup>−14</sup>
# (''ababb'')<sup>−14</sup>''ababbb''
# (''ababb'')<sup>−14</sup>''ababbb''(''ababb'')<sup>14</sup>
{{col-break}}
# ''a''&nbsp;— твірна.
# ''b''&nbsp;— твірна.
# Друге правило: (1).(2)
# Друге правило: (3).(2)
# Друге правило: (3).(4)
# Друге правило: (5).(2)
# Друге правило ітеровано: (4) повторено 18 разів
# Третє правило: (7) обернення
# Друге правило: (8).(2)
# Друге правило: (9).(7)
# Друге правило ітеровано: (5) повторено 14 разів
# Третє правило: (11) обернення
# Друге правило: (12).(6)
# Друге правило: (13).(11)
{{col-end}}

== Застосування ==
''Короткі описи скінченних груп''. Лінійні програми можна використовувати для вивчення стиснення скінченних груп за допомогою [[Логіка першого порядку|логіки першого порядку]]. Вони надають засіб для побудови «коротких» речень, що описують <math>G</math> (тобто значно коротших, ніж <math>| G |</math>). Детальніш, ЛП використовують, щоб довести, що кожна скінченна проста група має опис першого порядку довжини <math>O (log| G |)</math>, а кожна скінченна група <math>G</math> має опис першого порядку довжини <math>O (log^3 | G | )</math><ref>{{Cite journal|last=Nies|first=André|last2=Tent|first2=Katrin|date=2017|title=Describing finite groups by short first-order sentences|journal=[[Israel Journal of Mathematics]]|volume=221|pages=85–115|arxiv=1409.8390|doi=10.1007/s11856-017-1563-2|doi-access=free}}</ref>.

''Лінійні програми обчислення твірних для максимальних підгруп скінченних простих груп''. Онлайновий АТЛАС представлень скінченних груп<ref>{{Cite web|url=http://brauer.maths.qmul.ac.uk/Atlas/v3/|title=ATLAS of Finite Group Representations - V3}}</ref> містить абстрактні лінійні програми для обчислення твірних наборів максимальних підгруп для багатьох скінченних простих груп.

'''Приклад''': група <math>Sz(32)</math>, що належить до нескінченної сім'ї {{Нп|Групи Сузукі|груп Сузукі|en|Suzuki groups}}, має ранг 2 через твірні <math>a</math> і <math>b</math>, де <math>a</math> має порядок 2, <math>b</math> має порядок 4, <math>ab</math> має порядок 5, <math>ab^2</math> має порядок 25 і <math>abab^2ab^3</math> має порядок 25. Нижче наведено лінійну програму, яка обчислює твірний набір для максимальної підгрупи <math>E32 \cdot E32 \rtimes C31</math>. Цю лінійну програму можна знайти в онлайновому АТЛАСІ представлень скінченних груп.{{Col-begin}}
{{Col-break}}
# α
# β
# α<sup>2</sup>
# α<sup>2</sup>β
# α<sup>2</sup>βα
# α<sup>2</sup>βαβ
# α<sup>2</sup>βαβα<sup>2</sup>βαβ
{{Col-break}}
# (1 2 3 4 5 6)
# (1 2)
# (1 3 5)(2 4 6)
# (1 3 5 2 4 6)
# (1 4)(2 5 3 6)
# (1 4 2 5 3 6)
# (1 2 3)(4 5 6)
{{Col-break}}
# α&nbsp;— твірна
# β&nbsp;— твірна
# Друге правило: (1).(1)
# Друге правило: (3).(2)
# Друге правило: (4).(1)
# Друге правило: (5).(2)
# Друге правило: (6).(6)
{{Col-end}}

== Теорема про досяжність ==
Теорема про досяжність стверджує, що для скінченної групи <math>G</math>, породженої <math>S</math>, кожна <math> g \in G</math> має максимальну вартість <math>(1+lg|G|)^2</math>. Це можна розуміти як обмеження того, наскільки складно згенерувати елемент групи з генераторів.

Тут функція <math>lg(x)</math>&nbsp;— це цілочисельна версія функції логарифма: нехай для <math>k \geq 1</math> <math>lg(k) = max \{r: 2^r \leq k\}</math>.

Ідея доведення полягає в тому, щоб побудувати множину <math>Z = \{ z_1 ,..., z_s \}</math>, яка працюватиме як нова твірна множина (<math>s</math> буде визначено в процесі). Зазвичай вона більша за <math>S</math>, але будь-який елемент <math>G</math> можна виразити як слово довжини щонайбільше <math>2|Z|</math> над <math>Z</math>. Множина <math>Z</math> будується індуктивним визначенням зростальної послідовності множин <math>K (i)</math>.

Нехай <math>K ( i ) = \{ z_1 ^ {\alpha_1} \cdot z_2 ^ {\alpha_2} \cdot ... \cdot z_j ^ {\alpha_j} : {\alpha_i} \in \{ 0,1 \} \}</math>, де <math>z_i</math>&nbsp;— елемент групи, доданий до <math>Z</math> на <math>i</math>-му кроці. Нехай <math>c(i)</math> позначає довжину найкоротшої лінійної програми, яка містить <math>Z ( i ) = { z_1 ,..., z_i }</math>. Нехай <math>K (0) = { 1_G }</math> і <math>c (0)=0</math>. Ми визначаємо множину <math>Z</math> рекурсивно:

* Якщо <math>K ( i ) ^ {-1} K ( i ) = G</math>, оголосимо <math>s</math> рівним <math>i</math>, і зупинимося.
* В іншому випадку виберемо деяке <math>z_{i + 1} \in G \backslash K ( i ) ^ {-1} K ( i )</math> (яка непорожня), яке мінімізує «збільшення вартості» <math>c ( i +1) - c ( i )</math>.

За допомогою цього процесу <math>Z</math> визначається так, що будь-яке <math>g \in G</math> можна записати як елемент <math>K ( i ) ^ {-1} K ( i )</math>, що фактично полегшує генерування із <math>Z</math>.

Тепер, щоб переконатися, що процес завершується протягом <math>lg(| G |)</math> кроків, потрібно перевірити таке твердження:

{{Теорема|1='''Твердження 1'''. Якщо <math>i < s</math>, то <math> \left \vert K(i+1) \right \vert </math> = <math> 2 \left \vert K(i) \right \vert </math>.}}
{{Доведення1| 
Очевидно, що <math>\left \vert K(i+1) \right \vert \leq 2\left \vert K(i) \right \vert</math>. Тепер припустимо, що <math>\left \vert K(i+1) \right \vert < 2\left \vert K(i) \right \vert</math>. За [[Принцип Діріхле|принципом Діріхле]] <math>k_1, k_2 \in K(i+1)</math> де <math>k_1 = z_1 ^ {\alpha_1} \cdot z_2 ^ {\alpha_2} \cdot ... \cdot z_{i+1} ^ { \alpha_{i+1} } = z_1 ^ {\beta_1} \cdot z_2 ^ {\beta_2} \cdot ... \cdot z_{i+1} ^ {\beta_{i+1} } = k_2</math> для деяких <math>\alpha_j, \beta_j \in \{ 0,1 \}</math>. Нехай <math>r</math> - найбільше ціле число, таке що <math>\alpha_r \neq \beta_r</math>. Припустимо, без втрати загальності, що <math>\alpha_r = 1</math>. З цього випливає, що <math>z_r = z_p^{- \alpha_p} \cdot z_{p-1}^{- \alpha_{p -1} } \cdot ... \cdot z_1^{-\alpha_1} \cdot z_1^{\beta_1} \cdot z_2^{\beta_2} \cdot ... \cdot z_q^{\beta_q}</math>, де <math>p,q < r</math>. Отже, <math>z_r \in { K (r - 1) ^ {-1}  K (r - 1) }</math> - маємо суперечність.|title=Доведення|expanded=1}}&nbsp;
Наступне твердження використовують, щоб показати, що вартість кожного елемента групи міститься в необхідних межах.
{{Теорема|'''Твердження 2'''. <math> c(i) \leq i^2 - i</math>.}}
{{Доведення1|Оскільки <math>c(0)=0</math>, достатньо показати, що <math>c(i+1) - c(i) \leq 2i</math>. [[Граф Келі]] для <math>G</math> зв'язний і, якщо <math>i < s</math>, <math>K(i)^{-1} K(i) \neq G</math>, то є елемент форми <math>g_1 \cdot g_2 \in G \backslash K(i)^{-1}K(i)</math> де <math>g_1 \in K(i)^{-1} K(i)</math> і <math>g_2 \in S</math>.|title=Доведення|expanded=1}}
Для створення <math>g_1 \in K ( i ) ^ {-1} K ( i )</math> потрібно щонайбільше <math>2 i</math> кроків. Немає сенсу генерувати елемент максимальної довжини, оскільки це тотожність. Отже, достатньо <math>2i-1</math> кроків. Для створення <math>g_1 \cdot g_2 \in G \backslash K ( i ) ^ {-1} K ( i )</math> достатньо <math>2i</math> кроків.

Тепер закінчуємо теорему. Оскільки <math>K ( s ) ^ {-1} K ( s ) = G</math>, будь-яке <math>g \in G</math> можна записати у вигляді <math>k_1 ^ {-1} \cdot k_2</math>, де <math>k_1 ^ {-1} , k_2 \in K(s)</math>. Згідно з наслідком 2, нам потрібно щонайбільше <math>s^2 - s</math> кроків, щоб згенерувати <math>Z ( s ) = Z</math>, і не більше <math>2s - 1</math> кроків, щоб згенерувати <math>g</math> із <math>Z ( s )</math>.

Тому <math>c(g|S) \leq s^2 + s - 1 \leq lg^2|G| + lg|G| - 1 \leq (1 + lg|G|)^2</math>.

== Примітки ==
{{Reflist}}
[[Категорія:Теорія складності обчислень]]
[[Категорія:Теорія груп]]