Проблема равенства слов в группах

Проблема равенства слов в группах — раздел комбинаторики и алгебраической теории полугрупп (а также теории групп), изучающий вопрос о том, можно ли в данной группе (или полугруппе, моноиде) две формально различные записи (слова в алфавите образующих) считать равными на основании заданных определяющих соотношений. Формально, проблема равенства слов формулируется как задача построения алгоритма, который для любых двух слов над алфавитом порождающих элементов группы по её заданию (например, в виде конечной презентации) за конечное число шагов определяет, задают ли эти слова один и тот же элемент группы.

Эта задача является одной из трёх классических алгоритмических проблем теории групп, сформулированных Максом Деном в 1911 году (наряду с проблемой сопряжённости и проблемой изоморфизма). Проблема равенства слов стала ключевым объектом исследований в теории алгоритмов и теории вычислимости, поскольку, как было установлено П. С. Новиковым в 1955 году, в общем виде она алгоритмически неразрешима.

Формальная постановка

Пусть группа G задана конечной презентацией:

G = ⟨ x1, x2, …, xn | R1, R2, …, Rm ⟩,

где {x1, …, xn} — порождающие элементы, а {R1, …, Rm} — определяющие соотношения (слова в алфавите образующих и их формальных обратных, которые постулируются равными единице группы). Произвольное слово w в алфавите X ∪ X⁻¹ (где X⁻¹ — формальные символы обратных элементов) называется представляющим словом для некоторого элемента группы. Проблема равенства слов для данной презентации заключается в следующем: существует ли алгоритм, который для любого слова w над X ∪ X⁻¹ за конечное число шагов отвечает, представляет ли w единицу группы (т. е. истинно ли, что w = 1 в G).

Эквивалентная формулировка: существует ли алгоритм, решающий, задают ли два произвольных слова u и v один и тот же элемент группы (u = v в G), что сводится к проверке равенства uv⁻¹ = 1.

История и основные результаты

До середины XX века проблема равенства слов считалась чисто алгебраической задачей, для некоторых классов групп были найдены частные решения:

• Конечно порождённые абелевы группы. Для них проблема разрешима (алгоритм основан на приведении матрицы экспонент к нормальной форме Смита).
• Свободные группы. Проблема разрешима: два слова равны в свободной группе тогда и только тогда, когда их свободно редуцированные формы (после удаления подстрок вида xx⁻¹ и x⁻¹x) совпадают.
• Конечные группы. Проблема разрешима тривиально (перебором элементов), но практические алгоритмы используют таблицы умножения или представление Кэли.

В 1955 году Павел Сергеевич Новиков опубликовал работу «Об алгоритмической неразрешимости проблемы равенства слов в теории групп», в которой доказал существование конечно определённой группы (т. е. заданной конечным числом порождающих и конечным числом соотношений), для которой не существует общего алгоритма, решающего проблему равенства слов. Это был один из первых в мире результатов об алгоритмической неразрешимости алгебраической задачи.

Впоследствии (1958, 1959) Уильям Бун независимо получил аналогичный результат, построив свою конструкцию неразрешимой группы. Позже было показано, что даже для конечно определённых полугрупп проблема равенства слов может быть неразрешимой.

Несмотря на общую неразрешимость, для многих важных классов групп проблема равенства слов разрешима:

• Конечно порождённые нильпотентные группы — разрешима (Мальцев, 1960).
• Конечно порождённые разрешимые группы — в общем случае неразрешима (отрицательный результат для некоторых разрешимых групп был получен в 1980-х годах), но для отдельных подклассов (например, полициклических) разрешима.
• Группы с одним определяющим соотношением — разрешима (теорема Магнуса, 1932).
• Гиперболические группы в смысле Громова — разрешима за линейное время.
• Группы кос — разрешима.
• Конечно порождённые подгруппы в группах GL(n, Z) (линейные группы над целыми числами) — разрешима (по теореме о разрешимости проблемы равенства для произвольной конечно определённой линейной группы, доказанной в 1980-х).

Технические аспекты

Определители и редукция

Решение проблемы равенства слов для конкретной группы обычно сводится к построению канонической формы (нормальной формы) каждого элемента. Если можно указать алгоритм, который по любому слову w строит некоторую единственную запись элемента, то два слова представляют один и тот же элемент группы тогда и только тогда, когда их нормальные формы совпадают.

Для свободных абелевых групп нормальной формой служит запись вида x1^{a1} x2^{a2} … xn^{an}, где ai — целые числа. Для нильпотентных групп используется представление с помощью базисов Мальцева. Для групп кос — представление в виде слов в системе порождающих Артина и комбинаторная редукция с помощью соотношений кос.

Алгоритмическая сложность

Даже когда проблема равенства слов разрешима, её вычислительная сложность может оказаться очень высокой:

• Для нильпотентных групп ступени 2 (например, группы Гейзенберга) существует алгоритм с полиномиальной сложностью.
• Для некоторых групп с экспоненциально растущим объёмом шара (например, слово гиперболических групп) сложность может быть экспоненциальной, но в среднем линейной.
• Существуют конечно определённые группы, для которых любой алгоритм решения проблемы равенства слов требует времени, растущего как функция Аккермана (жалкий рост, доказанный Дж. Бринксом и другими; известно, что для некоторых групп экспоненциальный рост длины слова при редукции приводит к сверхэкспоненциальным затратам времени).

Связь с другими алгоритмическими проблемами

Проблема равенства слов тесно связана с проблемой сопряжённости (существует ли элемент, переводящий одно слово в другое сопряжением) и проблемой изоморфизма (эквивалентны ли две презентации одной группы). Для разрешимых и нильпотентных групп из разрешимости проблемы равенства часто следует разрешимость и сопряжённости, но не всегда наоборот.

Известно, что для конечно определённых групп разрешимость проблемы равенства слов не влечёт автоматически разрешимости проблемы сопряжённости (пример — некоторые группы Баумслага—Солитера). Однако для гиперболических групп обе проблемы разрешимы, и время работы алгоритмов полиномиально.

Практическое значение

Хотя проблема равенства слов возникла из чисто теоретических интересов, её приложения обнаружились в компьютерной алгебре и теории автоматов:

• Системы компьютерной алгебры (GAP, Magma) используют алгоритмы решения проблемы равенства слов для работы с группами, заданными порождающими и соотношениями.
• Теория формальных языков и автоматы: проблема равенства слов эквивалентна задаче проверки эквивалентности двух слов в моноиде, заданном конгруэнции; это имеет прямое отношение к разрешимости автоматов и полугрупп, порождённых конечными автоматами.
• В криптографии (например, в схемах на основе групп Брауэра) проблема равенства слов используется для создания односторонних функций (хотя на практике групповых алгоритмов хватает для атак).
• В теории вычислений проблема равенства слов для полугрупп — один из классических примеров алгоритмически неразрешимой задачи, демонстрирующих границы вычислимости.

Обобщения и вариации

Проблема равенства в полугруппах

В теории полугрупп и моноидов аналогичная проблема носит название проблема равенства слов в полугруппах. Для конечно порождённых и конечно определённых полугрупп она также может быть неразрешима (доказано А. Марковым в 1947 году). Однако существуют классы полугрупп, для которых она разрешима, например, коммутативные и нильпотентные полугруппы.

Проблема равенства слов для подгрупп

Рассматривается задача: можно ли по конечному набору порождающих подгруппы H в группе G определить, принадлежит ли данный элемент группы H? Для свободных групп эта проблема разрешима (алгоритм Нильсена—Шрайера), для произвольных конечно определённых групп — не разрешима в общем случае.

Проблема равенства для бесконечных слов

В теории бесконечных слов (ω-слов) также ставится задача равенства: два бесконечных слова равны, если они имеют одинаковую бесконечную последовательность. Для некоторых автоматических структур проблема алгоритмически разрешима.

Известные примеры неразрешимости

Самая первая конечно определённая группа с неразрешимой проблемой равенства слов была построена П. С. Новиковым. Конструкция была очень сложной (несколько сотен соотношений). Позже были найдены более простые примеры:

• Группа Хигмана (1961) — конечно определённая группа, все конечно порождённые подгруппы которой либо тривиальны, либо бесконечны; для неё проблема равенства неразрешима.
• Группа Буна—Новикова с 38 порождающими и 88 соотношениями (версия, упрощённая Д. Коллинзом).
• Существуют примеры с 2 порождающими и конечным числом соотношений (неразрешимость для 2-порождённых групп установлена Г. С. Маканиным и Ю. И. Мерзляковым; для конкретного вида соотношений).

Источники

• Новиков П. С. Об алгоритмической неразрешимости проблемы равенства слов в теории групп // Труды Математического института им. В. А. Стеклова. — 1955. — Т. 44. — С. 3–143.
• Бун У. Т. Проблема равенства слов в теории групп // Математика. Сборник переводов. — 1959. — Т. 3, № 4. — С. 117–135.
• Магнус В., Каррас А., Солитэр Д. Комбинаторная теория групп. — М.: Наука, 1974.
• Линдон Р., Шупп П. Комбинаторная теория групп. — М.: Мир, 1980.
• Хартли Б., Миллер С. (ред.) Алгоритмические проблемы теории групп. — Новосибирск: Наука (Сибирское отделение), 1984.
• Маканин Г. С. Проблема равенства слов в группах и полугруппах — история и современное состояние // Алгебра и логика. — 2001. — Т. 40, № 5. — С. 513–546.