Ist abelsche Gruppenisomorphie in ?

Ein -Laufzeitalgorithmus für den abelschen Gruppenisomorphismus ist leicht zu erkennen. Später an diesem Problem im Jahr 2003 arbeiten Vikas verbessern das Ergebnis von Laufzeit auf . Im Jahr 2007 zeigte Kavitha , dass der Isomorphismus der abelschen Gruppe in linearer Zeit, dh in -Zeit, durchgeführt werden kann .O ( n 2 ) O ( n log n ) O ( n $O(n^2)$$O(n^2)$$O(n \log n)$$O(n)$

Ich weiß, dass der abelsche Gruppenisomorphismus, wenn Gruppen durch Tabellendarstellung angegeben werden, in . Gibt es eine Forschungsarbeit oder einen Artikel, der / der zeigt, dass er sich in ? Ich habe versucht zu googeln, aber nur das Ergebnis erhalten, dass es in . A C 0 T C $\mathsf{TC^0}$$\mathsf{AC^0}$$\mathsf{TC^0}$

Frage: Ist der abelsche Gruppenisomorphismus (Gruppen in Tabellendarstellung angegeben) in$\mathsf{AC^0}$

Im Gegensatz zu dem, was in der Frage angegeben ist, ist nicht bekannt, dass sich der abelsche Gruppenisomorphismus in . Dies bedeutet natürlich auch, dass nicht bekannt ist, dass es sich um A C 0 handelt .$\mathrm{TC^0}$$\mathrm{AC^0}$

Was ist bekannt , ist die folgende Beobachtung aus [1]. Es sei das folgende Problem: Wenn eine Multiplikationstabelle einer abelschen Gruppe ( A , ⋅ ) gegeben ist , bestimmen die Elemente und in unär, ob . Der Struktursatz für endliche abelsche Gruppen impliziert leicht, dass wenn zwei solche Gruppen der Größe n sind , dann$\mathrm{pow}$$(A,{\cdot})$$a,b\in A$b = a m A , $m$$b=a^m$$A,B$$n$

Da wir in Mengen mit Polynomgröße zählen können , erhalten wir$\mathrm{TC^0}$

Satz 1: Der Isomorphismus der abelschen Gruppe ist in berechenbar .$\mathrm{TC^0(pow)}$

Nun ist in L klar berechenbar und, wie in [2] gezeigt, auch in der Klasse FOLL. Somit,$\mathrm{pow}$

Folgerung 2: Der Isomorphismus der abelschen Gruppe ist in und in T C 0 ( F O L L ) berechenbar .$\mathrm{L}$$\mathrm{TC^0(FOLL)}$

Es ist nicht bekannt, ob in T C 0 berechenbar ist .$\mathrm{pow}$$\mathrm{TC^0}$

Es scheint, dass Korollar 2 das bekannteste Ergebnis ist, wenn es um die üblichen Schaltungsklassen mit „Polynomgröße“ geht. Ich stelle jedoch fest, dass das Problem in der quasipolynomialen Version von :$\mathrm{AC^0}$

Satz 3: Der Isomorphismus der abelschen Gruppe kann durch eine einheitliche Folge von Booleschen Schaltungen mit konstanter Tiefe und Quasipolynomgröße berechnet werden. genauer gesagt ist es in .$\Sigma_2\text-\mathrm{TIME}\bigl((\log n)^2\bigr)$

(Dies führt zu einer einheitlichen Familie von Tiefen-3-Schaltkreisen der Größe , bei denen die unteren Disjunktionen nur O ( ( log n ) 2 ) einfächern . Dies wird häufig als „Tiefe 2 $2^{O((\log n)^2)}$$O\bigl((\log n)^2\bigr)$ ”.)$2\frac12$

Satz 3 ist wiederum eine Konsequenz des Struktursatzes für endliche abelsche Gruppen: Jede solche Gruppe kann als direkte Summe von -zyklischen Untergruppen geschrieben werden, daher sind die Gruppen A und B isomorph, wenn sie als direkte Summen von geschrieben werden können zyklische Untergruppen mit übereinstimmenden Ordnungen: das heißt, wenn | A | = | B | = n , dann A ≃ B iff$O(\log n)$$A$$B$$|A|=|B|=n$$A\simeq B$

es gibt

• eine Folge von k ≤ log n ganzen Zahlen m i ≤ $\{m_i:i<k\}$$k\le\log n$$m_i\le n$

• Sequenzen und { b i : i < k } ⊆ $\{a_i:i<k\}\subseteq A$$\{b_i:i<k\}\subseteq B$

so dass

• $\prod_{i<k}m_i=n$

• und b m i i = 1 für jedes i < $a_i^{m_i}=1$$b_i^{m_i}=1$$i<k$

• für alle Folgen von ganzen Zahlen 0 ≤ r i < m i , nicht alle Nullen:$\{r_i:i<k\}$$0\le r_i<m_i$

  und ∏ i < k b r i i ≠ $\prod_{i<k}a_i^{r_i}\ne1$$\prod_{i<k}b_i^{r_i}\ne 1$

Die beiden Hauptquantifizierer sind hervorgehoben. Um zu sehen, dass die angegebenen Grenzen nicht überschritten werden, müssen wir zeigen, dass die Identitäten in N T I M E ( ( log n ) 2 ) überprüft werden können . Dies kann durch sukzessives Erraten und Überprüfen der Werte der Teilprodukte ∏ i < l a r i i für l = 0 , … , k erfolgen ; außerdem für jedes $\prod_{i<k}a_i^{r_i}=1$$\mathrm{NTIME}\bigl((\log n)^2\bigr)$$\prod_{i<l}a_i^{r_i}$$l=0,\dots,k$$i$In ähnlicher Weise erraten und verifizieren wir Teilergebnisse der Berechnung von a r i i durch wiederholtes Quadrieren. Insgesamt ergibt dies O ( ∑ i log r i ) ⊆ O ( ∑ i log m i ) ⊆ O ( log n ) Vermutungen, deren Überprüfung jeweils O ( log n ) Zeit in Anspruch nimmt.$O(\log r_i)$$a_i^{r_i}$$O\left(\sum_i\log r_i\right)\subseteq O\left(\sum_i\log m_i\right)\subseteq O(\log n)$$O(\log n)$

Es gibt einen anderen Weg, um Satz 3 zu beweisen: Beachten Sie, dass wir in nur m betrachten müssen , die Primkräfte sind: m = p e . In diesem Fall haben die beiden beleidigenden Mengen, die wir zählen müssen, auch Größen, die Potenzen von p sind ; insbesondere wenn sie ungleich sind, unterscheiden sie sich um einen Faktor von mindestens p . Somit reicht es aus, die Größen der beiden Sätze ungefähr zu zählen . Dies kann im Quasipolynom A C 0 unter Verwendung des Sipser-Codierungs-Lemmas erfolgen. Und wie ich bereits gezeigt habe, kann p o w in Quasipolynom A berechnet werden$(*)$$m$$m=p^e$$p$$p$$\mathrm{AC^0}$$\mathrm{pow}$ durch wiederholtes Quadrieren.$\mathrm{AC^0}$

Eine Konsequenz von Satz 3 ist, dass, wenn sich herausstellt, dass das abelsche Isomorphismusproblem nicht in , dies ziemlich schwierig zu beweisen sein könnte: Insbesondere kann man PARITÄT oder MEHRHEIT nicht einfach auf das Problem reduzieren, da diese eine exponentielle Größe erfordern Schaltkreise mit begrenzter Tiefe, nicht quasipolynomisch. Selbst wenn wir versuchen, die PARITÄT auf m ≪ n Bits auf das Problem zu reduzieren , gibt es nicht viel Raum für die Parameter: Insbesondere ist die PARITÄT von superpolylogarithmisch vielen Bits nicht durch Schaltungen mit konstanter Tiefe quasipolynomialer Größe und die PARITÄT von polylogarithmisch zu berechnen Viele Bits sind in A C 0 bereits durch Teilen und Erobern berechenbar .$\mathrm{AC^0}$$m\ll n$$\mathrm{AC^0}$

Verweise:

[1] Arkadev Chattopadhyay, Jacobo Torán, Fabian Wagner: Der Graphisomorphismus ist nicht -reduzierbar für den Gruppenisomorphismus$\mathrm{AC^0}$ , ACM Transactions on Computation Theory 5 (2013), No. 4, Artikel-Nr. 13, doi: 10.1145 / 2540088 .

[2] David Mix Barrington, Peter Kadau, Klaus-Jörn Lange und Pierre McKenzie: Zur Komplexität einiger Probleme bei der Eingabe von Gruppen als Multiplikationstabellen , Journal of Computer and System Sciences 63 (2001), Nr. 2, S. 186–200, doi: 10.1006 / jcss.2001.1764 .