Was ist die schwierigste Instanz für das Problem des Gruppenisomorphismus?

11

Zwei Gruppen (G,) und (H,×) gelten als isomorph, wenn ein Homomorphismus von G nach H vorliegt , der bijektiv ist. Das Problem des Gruppenisomorphismus ist wie folgt: Überprüfen Sie bei zwei Gruppen, ob sie isomorph sind oder nicht. Es gibt verschiedene Möglichkeiten, eine Gruppe einzugeben. Die beiden am häufigsten verwendeten werden von einer Cayley-Tabelle und einem Generator verwendet. Hier gehe ich davon aus, dass Eingabegruppen durch ihre Cayley-Tabelle angegeben werden. Formeller:

Group Isomorphism Problem

Input :  Zwei Gruppen(G,) und(H,×) .

Decide :  IstGH ?

Nehmen wir an, dass n=|G|=|H|

Es ist nicht bekannt, dass das Problem des Gruppenisomorphismus, wenn Eingabegruppen durch die Cayley-Tabelle angegeben werden, im Allgemeinen in P . Obwohl es Gruppenklassen wie die abelsche Gruppenklasse gibt, für die das Problem bekanntermaßen in Polynomzeit liegt, Gruppen, die die Erweiterung einer abelschen Gruppe darstellen, einfache Gruppen usw. Selbst für Gruppen mit nullpotenter Klasse zwei gibt es keinen besseren Algorithmus als Brute Force bekannt.

Ein Brute-Force-Algorithmus für den Gruppenisomorphismus wird von Tarjan wie folgt angegeben. Lassen G und H sind zwei Eingangsgruppen, und lassen S eine Stromerzeugers der Gruppe sein G . Es ist bekannt, dass jede endliche Gruppe eine Menge von O(logn) -Größen zulässt , die in Polynomzeit gefunden werden kann. Die Anzahl der Bilder des Erzeugungssatzes S im Homomorphismus von G nach H beträgt nlogn viele. Überprüfen Sie nun, ob jeder mögliche Homomorphismus bijektiv ist oder nicht. Die Gesamtlaufzeit beträgt nlogn+O(1) .

Lassen Sie mich zunächst das Zentrum der Gruppe G :

Z(G)={gGag=ga,aG}

Z(G) bezeichnet die Elemente der GruppeG die mit allen anderen Elementen der GruppeG pendeln. Gruppen, für dieG/Z(G) (/ für Quotient verwendet) abelisch ist, werden als nicht potente Klasse-2-Gruppen bezeichnet. Mir scheint, dass nilpotente Gruppen der Klasse zwei die schwierigsten Instanzen sind, um das Problem des Gruppenisomorphismus zu lösen. Die Bedeutung von "schwierigsten Instanzen" ist: Durch die Lösung dieses Falls können Forscher, die in der Gruppentheorie arbeiten, das Isomorphismusproblem einer großen Anzahl von Gruppen lösen.

Anfangs dachte ich, dass einfache Gruppen die schwierigsten Instanzen sind, da sie Bausteine ​​aller Gruppen sind, aber später erfuhr ich, dass das Isomorphismusproblem für einfache Gruppen in P .

Frage : Was ist die schwierigste Instanz für das Problem des Gruppenisomorphismus?

aaaa
quelle
Hallo, könnten Sie erwägen, Ihre Frage ein wenig zu erweitern, um die Definition des Gruppenisomorphismusproblems (was ist die Eingabe, was ist die Ausgabe) und / oder eine Referenz zu rekapitulieren? Könnten Sie auch erwägen, die Definition des Zentrums einer Gruppe zu rekapitulieren? Könnten Sie zum Schluss klarstellen, ob "Erlauben, zu lösen" ("uns"?) Eine Behauptung über die Existenz einer Reduzierung ist?
a3nm

Antworten:

15

ppp>2p=2

0) Praktische Erfahrung (siehe Artikel von Newman, Eick, O'Brien, Holt, Cannon, Wilson, ..., die die in GAP und MAGMA implementierten Algorithmen angeben).

pFpTIppc<ppp

pRad(G)G/Rad(G)Rad(G)nO(loglogn)nlognpp

nn(227+o(1))μ(n)2μ(n)npn=pmp(227+o(1))m2ppnpn

pp

pppppc<p

Joshua Grochow
quelle
p
Ja, Nullpotenzklasse.
Joshua Grochow
Danke für die Klarstellung!
Vincent