В математике , а именно в вычислительной алгебре , прямолинейная программа ( SLP ) для конечной группы G = ⟨ S ⟩ — это конечная последовательность L элементов G , такая, что каждый элемент L либо принадлежит S , либо является обратным предшествующий элемент или произведение двух предшествующих элементов. Говорят, что SLP L вычисляет групповой элемент g ∈ G , если g ∈ L , где g кодируется словом в Sи его обратные.
Интуитивно, SLP, вычисляющая некоторый g ∈ G , является эффективным способом хранения g как группового слова над S ; обратите внимание, что если g строится за i шагов, длина слова g может быть экспоненциальной по i , но длина соответствующего SLP линейна по i . Это имеет важные приложения в вычислительной теории групп , поскольку SLP используются для эффективного кодирования групповых элементов в виде слов в заданном порождающем наборе.
Прямые программы были введены Бабаем и Семереди в 1984 году [1] как инструмент для изучения вычислительной сложности некоторых свойств группы матриц. Бабаи и Семереди доказывают, что каждый элемент конечной группы G имеет SLP длины O (log 2 | G |) в каждом множестве образующих.
Эффективное решение конструктивной проблемы принадлежности имеет решающее значение для многих теоретико-групповых алгоритмов. В терминах SLP это можно сформулировать следующим образом. Для конечной группы G = ⟨ S ⟩ и g ∈ G найдите программу прямой линии, вычисляющую g над S . Проблема конструктивного членства часто изучается в контексте групп черного ящика . Элементы кодируются битовыми строками фиксированной длины. Для теоретико-групповых функций умножения, обращения и проверки на равенство с тождеством предусмотрены три оракула . Алгоритм черного ящикаэто тот, который использует только эти оракулы. Следовательно, прямолинейные программы для групп черного ящика являются алгоритмами черного ящика.
Явные прямолинейные программы даны для множества конечных простых групп в онлайн- атласе конечных групп .
Пусть G — конечная группа и пусть S — подмножество G . Последовательность L = ( g 1 ,…, g m ) элементов G называется линейной программой над S , если каждый g i может быть получен по одному из следующих трех правил: