Gruppenisomorphismus zu Graphismorphismus

Beim Lesen einiger Blogs über die Komplexität von Berechnungen (zum Beispiel hier ) habe ich die Vorstellung übernommen, dass es einfacher ist, zu entscheiden, ob zwei Gruppen isomorph sind, als zwei Diagramme auf Isomorphismus zu testen. Auf der angegebenen Seite heißt es beispielsweise, dass der Graphisomorphismus ein allgemeineres Problem ist als der Gruppenisomorphismus.

Daher stelle ich folgendes vor

Bei einer gegebenen Gruppe kann jemand eine Konstruktion eines Graphen des Größenpolynoms inso dass für die Gruppen und$G$$\Gamma(G)$$|G|$

$$\Gamma(G) \cong \Gamma(H) \iff G \cong H$$ $G$$H?$

Die Reduktion ist in einem klassischen Aufsatz von Miller beschrieben.

Nicht so schnell. Hier lauert eine große Unklarheit:

Wie geben Sie Ihre Gruppe zur Berechnung ein?

Im Gegensatz zu Diagrammen können Gruppen als Mittel eingegeben werden, die sich hinsichtlich der Eingabegröße und der daraus resultierenden Komplexität erheblich unterscheiden. Die in Miller zitierte Version ist eine der am wenigsten natürlichen und wird beispielsweise in einem Computeralgebrasystem wie GAP, Magma oder Sage nicht vorkommen. Also, obwohl es eine theoretische Prämisse hat, würde es zu weit gehen, dies als Lösung des Problems zu bezeichnen.

1. Generatoren und Beziehungen: Der Gruppenisomorphismus ist unentscheidbar (der Graphisomorphismus ist entscheidbar).

$G$$G=1$

Für Gruppen, die von Generatoren und Relationen eingegeben werden: Gruppenisomorphismus ist schwieriger als Graphisomorphismus, tatsächlich unentscheidbar.

2. Eingaben, die von Softwaresystemen verwendet werden: Gruppenisomorphismus von Permutations- und Matrixgruppen ist mindestens so hart wie Graphisomorphismus (nicht umgekehrt).

$p$

Für Gruppeneingaben für Softwaresysteme gilt: Der Gruppenisomorphismus ist mindestens so hart wie der Graphisomorphismus.

3. Theoretische Komplexitätseingaben: Für eine Black-Box-Gruppeneingabe ist nicht bekannt, dass der Gruppenisomorphismus in NP oder co-NP vorliegt (der Graphisomorphismus ist in beiden).

$\Sigma^2$$f:G\to H$$G$$H$$f$ist ein gültiger Homomorphismus. Zumindest scheinen Sie eine Präsentation der Gruppen zu benötigen, und das ist nicht einfach zu erreichen.

Für Black-Box-Gruppen: Der Gruppenisomorphismus ist mindestens so hart wie der Graphisomorphismus.

4. Cayley-Tabelleneingaben.

Irgendwann in den 1970er Jahren beobachteten Tarjan, Pultr-Hederlon, Miller und andere, dass Gruppen, die über ihre gesamte Multiplikationstabelle eingegeben wurden, auch als Diagramme behandelt werden konnten. Auf diese Weise reduziert sich der Gruppenisomorphismus in der Polynomzeit auf den Graphisomorphismus. Miller ging noch viel weiter und stellte fest, dass zahlreiche kombinatorische Strukturen dasselbe tun, zum Beispiel Steiner-Tripel. Er zeigte auch, dass der Halbgruppen-Isomorphismus dem Graph-Isomorphismus äquivalent ist.

$n^{O(\log n)}$

Für Cayley-Tabellen: Gruppenisomorphismus reduziert sich auf Graphisomorphismus.

$n$$O((\log n)^3)$

$n$$O(n^2 \log n)$