Todd-Coxeter-algoritme

In de groepentheorie, een deelgebied van de wiskunde, is het Todd-Coxeter-algoritme, in 1936 geconstrueerd door J.A. Todd en H.S.M. Coxeter, een algoritme voor het oplossen van het nevenklasse-opsomming-probleem. Gegeven een presentatie van een groep G door generatoren en relaties en een ondergroep H van G, somt het algoritme de nevenklassen van H op G op en beschrijft de permutatierepresentatie van G op de ruimte van de nevenklassen. Als de orde van een groep G relatief klein is en van de deelgroep H bekend is dat deze ongecompliceerd is (bijvoorbeeld een cyclische groep), dan kan het algoritme met de hand worden uitgevoerd en geeft het algoritme een redelijke beschrijving van de groep G. Met behulp van hun algoritme konden Coxeter en Todd aantonen dat bepaalde systemen van betrekkingen tussen generatoren van bekende groepen compleet zijn, dat wil zeggen systemen vormen van gedefinieerde relaties vormen.

Het Todd–Coxeter-algoritme kan worden toegepast op oneindige groepen. Het is bekend dat het algoritme in een eindig aantal stappen tot een einde komt, dit onder voorwaarde dat de index van H in G eindig is. Anderzijds wordt voor een algemeen paar, dat bestaat uit een groepspresentatie en een deelgroep de looptijd van het algoritme niet begrensd door enige berekenbare functie van de index van de deelgroep en de omvang van de invoergegevens.