Wyliczenie Coseta

W matematyce wyliczanie cosetów to problem liczenia cosetów podgrupy H grupy G podanej w postaci prezentacji . Jako produkt uboczny otrzymuje się reprezentację permutacyjną dla G na cosetach H . Jeśli H ma znany skończony porządek, wyliczenie coset daje również rząd G.

W przypadku małych grup czasami możliwe jest ręczne wyliczenie coset. Jednak w przypadku dużych grup jest to czasochłonne i podatne na błędy, dlatego zazwyczaj przeprowadza się je komputerowo . Wyliczanie kosetów jest zwykle uważane za jeden z podstawowych problemów obliczeniowej teorii grup .

Oryginalny algorytm wyliczania cosetów został wymyślony przez Johna Arthura Todda i HSM Coxetera . Zaproponowano różne ulepszenia oryginalnego algorytmu Todda-Coxetera , w szczególności klasyczne strategie V. Felscha i HLT (Haselgrove, Leech and Trotter). Praktyczne wdrożenie tych strategii z udoskonaleniami jest dostępne na stronie internetowej ACE. Algorytm Knutha – Bendixa może również wykonywać wyliczanie coset iw przeciwieństwie do algorytmu Todda – Coxetera może czasami rozwiązywać problem tekstowy dla nieskończonych grup.

Główne praktyczne trudności w tworzeniu modułu wyliczającego coset polegają na tym, że trudno lub niemożliwe jest przewidzenie, ile pamięci lub czasu będzie potrzebne do zakończenia procesu. Jeśli grupa jest skończona, to jej wyliczanie coset musi się ostatecznie zakończyć, chociaż może to zająć dowolnie dużo czasu i zużywać dowolną ilość pamięci, nawet jeśli grupa jest trywialna. W zależności od zastosowanego algorytmu może się zdarzyć, że dokonanie niewielkich zmian w prezentacji, które nie powodują zmiany grupy, ma jednak duży wpływ na ilość czasu lub pamięci potrzebnej do wykonania wyliczenia. Zachowania te są konsekwencją nierozwiązywalności problemu słownego dla grup .

Delikatne wprowadzenie do wyliczania coset znajduje się w tekście Rotmana o teorii grup. Bardziej szczegółowe informacje na temat poprawności, wydajności i praktycznej implementacji można znaleźć w książkach Simsa i Holta et al.