Перечисление смежных классов - Coset enumeration

В математика, перечисление смежных классов проблема подсчета смежные классы подгруппы ЧАС из группа грамм дано с точки зрения презентация. В качестве побочного продукта получается перестановочное представление за грамм на смежных классах ЧАС. Если ЧАС имеет известный конечный порядок, перечисление смежных классов дает порядок грамм также.

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

Оригинальный алгоритм перечисления смежных классов был изобретен Джон Артур Тодд и Х. С. М. Коксетер. Различные улучшения оригинала Алгоритм Тодда-Кокстера были предложены, в частности, классические стратегии В. Фельша и HLT (Haselgrove, Leech и Trotter). Практическая реализация этих стратегий с уточнениями доступна на сайте ACE.[1] В Алгоритм Кнута – Бендикса также может выполнять перечисление смежных классов и, в отличие от алгоритма Тодда – Кокстера, иногда может решать проблема со словом для бесконечных групп.

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

Мягкое введение в перечисление смежных классов дается в тексте Ротмана по теории групп.[2] Более подробную информацию о правильности, эффективности и практической реализации можно найти в книгах Sims.[3] и Holt et al.[4]

Рекомендации

  1. ^ ACE: Advanced Coset Enumerator от Джорджа Хаваса и Колина Рамзи В архиве 2007-09-01 на Wayback Machine
  2. ^ Ротман, Джозеф Дж. (1995). Введение в теорию групп. Springer. ISBN  0-387-94285-8.
  3. ^ Симс, Чарльз С. (1994). Вычисление с конечно представленными группами. Издательство Кембриджского университета. ISBN  0-521-43213-8.
  4. ^ Холт, Дерек Ф. (2005). Справочник по вычислительной теории групп. CRC Press. ISBN  1-58488-372-3.