Komplexität von Mitgliedschaftstests für endliche abelsche Gruppen

Betrachten Sie das folgende Problem beim Testen der Mitgliedschaft von Abelian-Untergruppen .

Eingänge:

1. Eine endliche abelsche Gruppe $G=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m}$ mit beliebig großem $d_i$ .

2. Ein Generatorsatz $\lbrace h_1,\ldots,h_n\rbrace$ eine Untergruppe $H\subset G$ .

3. Ein Element $b\in G$ .

Ausgang: ‚Ja‘ , wenn $b\in H$ und ‚Nein‘ an anderer Stelle‘.

Frage: Kann dieses Problem in einem klassischen Computer effizient gelöst werden ? Ich halte einen Algorithmus für effizient, wenn er $O(\text{polylog}|G|)$ und Speicherressourcen im üblichen Sinne klassischer Turing-Maschinen verwendet. Beachten Sie, dass wir für jede Untergruppe H annehmen können . Die Eingabegröße dieses Problems ist is log | G | ⌉ .$n= O(\log|G|)$$H$$\lceil \log|G|\rceil$

Ein bisschen Motivation . Intuitiv sieht es so aus, als könnte das Problem mit Algorithmen gelöst werden, um lineare Kongruenzsysteme oder lineare diophantische Gleichungen zu lösen (siehe unten). Es scheint jedoch, dass im Zusammenhang mit Berechnungen mit ganzen Zahlen verschiedene Begriffe der Recheneffizienz verwendet werden, wie z. Ich bin kein Experte für diese Definitionen und kann keine Referenz finden, die diese Frage eindeutig regelt.

Update: Die Antwort auf das Problem lautet "Ja".

• In einer späten Antwort schlug ich eine Methode vor, die auf normalen Smith-Formen basiert und für jede Gruppe mit der vorgeschriebenen Form effizient ist.

• Eine Antwort von Blondin zeigt, dass in dem speziellen Fall, in dem alle die Form d i = N e i i und $d_i$$d_i= N_i^{e_i}$ sind "kleine ganze Zahlen"dann gehört das Problem zu NC 3 ⊂ P . Winzige Ganzzahlen sind exponentiell klein mit der Eingabegröße: O ( log log | A | ) .$N_i, e_i$$\text{NC}^3\subset \text{P}$$O(\log\log|A|)$

In meiner Antwort habe ich "orthogonale Untergruppen" verwendet, um dieses Problem zu lösen, aber ich glaube, dass dies nicht notwendig ist. Ich werde versuchen, in Zukunft eine direktere Antwort auf die von mir gelesene Methode der Echelon-Formulare zu geben.

---

Einige mögliche Ansätze

Das Problem hängt eng mit der Lösung des linearen Kongruenzsystems und / oder der linearen Diophantingleichungen zusammen. Ich fasse diese Zusammenhänge der Vollständigkeit halber kurz zusammen.

Nehmen Sie als die Matrix, deren Spalten die Elemente der Erzeugungsmenge { h 1 , … , h n } sind . Das folgende Gleichungssystem$A$$\lbrace h_1, \ldots, h_n \rbrace$

$$Ax^{T}= \begin{pmatrix} h_1(1) & h_2(1) & \ldots & h_n(1)\\ h_1(2) & h_2(2) & \ldots & h_n(2)\\ \vdots & \vdots & \cdots & \vdots\\ h_1(m) & h_2(m) & \ldots & h_n(m) \end{pmatrix} \begin{pmatrix} x(1)\\ x(2)\\ \vdots\\ x(n) \end{pmatrix} = \begin{pmatrix} b(1) \\ b(2) \\ \vdots\\ b(m) \end{pmatrix} \begin{matrix} \mod d_1\\ \mod d_2\\ \vdots\\ \mod d_m \end{matrix}$$

wenn eine Lösung hat , und nur wenn .$b\in H$

Wenn alle zyklischen Faktoren die gleiche Dimension gibt es einen Algorithmus, der auf Smith-Normalformen basiert und das Problem in der Polynomzeit löst. In diesem Fall findet ein effizienter Algorithmus aus [1] die Smith-Normalform von A : Er gibt eine Diagonalmatrix D und zwei invertierbare Matrizen U und V zurück, so dass D = U A V ist . Dies reduzierte das Problem auf die Lösung des äquivalenten Systemsystems D Y = U $d=d_i$$A$$D$$U$$V$$D=UAV$ mit D- Diagonale. Wir können effizient entscheiden, ob das System eine Lösung mit dem euklidischen Algorithmus hat.$DY=Ub \mod d$$D$

Das obige Beispiel legt nahe, dass das Problem im allgemeinen Fall mit ähnlichen Techniken effizient gelöst werden kann. Wir können versuchen, das System durch modulare Operationen zu lösen oder indem wir das System in ein größeres System linearer diophantischer Gleichungen umwandeln. Einige mögliche Techniken, um das Problem anzugehen, das mir einfällt, sind:

1. Die Berechnung der Smith Normalformen von .$A$
2. Berechnen der Reihe Echelon Form .$A$
3. Ganzzahlige Gaußsche Eliminierung.

Verifizieren , ob (wobei h i Vektoren sind nach den Anmerkungen des OP) zum Verifizieren äquivalent ist , ob es eine Lösung für dieses System ist: ( h 1 ( 1 ) ⋯ h n ( 1 ) d e 1 1 0 ⋯ $b \in \langle h_1, \ldots, h_n\rangle$$h_i$

$$\begin{pmatrix} h_{1}(1) & \cdots & h_{n}(1) & d_1^{e_1} & 0 & \cdots & 0 \\\\ \vdots & \ddots & \vdots & \vdots & \vdots & \vdots & \vdots \\\\ h_{1}(m) & \cdots & h_{n}(m) & 0 & 0 & \cdots & d_m^{e_N} \end{pmatrix} \begin{pmatrix} x(1) \\\\ \vdots \\\\ x(n) \\\\ y(1) \\\\ \vdots \\\\ y(m) \end{pmatrix} \equiv \begin{pmatrix} b(1) \\\\ \vdots \\\\ b(m) \end{pmatrix}$$

In Ihrem Fall sind winzige Zahlen (dh ihr Wert ist in der Eingabegröße logarithmisch). Leider können wir nicht davon ausgehen, dass d 1 , … $e_1, \ldots, e_N$ winzig sind.$d_1, \ldots, d_n$

Wenn ja, können Sie in eine Lösung für das System aus einem Ergebnis von McKenzie & Cook [1] finden . Diese Arbeit zeigt, dass das Lösen linearer Kongruenzen modulo einer ganzen Zahl mit winzigen Faktoren (LCON) in NC 3 enthalten ist . Darüber hinaus ist dieses Problem NC 1 -äquivalent zu dem Problem der Mitgliedschaft in einer abelschen Permutationsgruppe (AGM). McKenzies Doktorarbeit widmet sich voll und ganz diesen Problemen [1] . In jüngerer Zeit wurden diese Probleme von Arvind & Vijayaraghavan [3] in Betracht gezogen .$\text{NC}^3$$\text{NC}^3$$\text{NC}^1$

[1] Pierre McKenzie & Stephen A. Cook. Die parallele Komplexität abelscher Permutationsgruppenprobleme. 1987.

[2] Pierre McKenzie. Parallele Komplexitäts- und Permutationsgruppen. 1984.

[3] V. Arvind & TC Vijayaraghavan. Klassifizieren von Problemen in linearen Kongruenzen und abelschen Permutationsgruppen mithilfe von Logspace-Zählklassen. 2010.

Nach einiger Zeit gelang es mir, einen vielleicht nicht optimalen, aber einfachen Algorithmus zu finden, der beweist, dass die Komplexität des Problems polynomisch ist.

Algorithmus

(a) Berechnen Sie einen Generatorsatz der orthogonalen Untergruppe von $H^{\perp}$$H$ .

(b) Prüfen Sie, ob das Element orthogonal zu H ⊥ ist oder nicht .$b$$H^{\perp}$

Es gibt effiziente klassische Algorithmen für die Probleme (a) und (b) (siehe Analyse unten). Dies ergibt einen effizienten Mitgliedschaftstest, da ein Element genau dann orthogonal zu H ⊥ ist, wenn h ∈ H ist .$b$$H^\perp$$h\in H$

---

Analyse

$H^{\perp}$$G$

$$H^{\perp}:= \{g\in G : \chi_g(h)=1\quad \forall h\in H \}$$

1. $H^{\perp}$$G$
2. $H^{\perp^\perp}=H$

Algorithmus für (a) :

$g$$H^{\perp}$$\chi_{g}(h)=1$$h\in H$, but, by linearity it is enough to show $\chi_{b}(h_i)=1$ for each generator of $H$. Expanding the character in terms of exponentials (here I implicitly use the cyclic factor decomposition) this condition is equivalent to

$$\begin{eqnarray} \exp \left\lbrace 2\pi i \left( \frac{g(1)h_{i}(1)}{d_1}+\ldots + \frac{g(m) h_{i}(m)}{d_m} \right) \right\rbrace=1 \end{eqnarray}$$ To solve these equations, compute $M:= \text{lcm}(N_1,\ldots,N_d)$ using the Euclidean algorithm and the numbers $\alpha_i:=M/d_i$. We can re-write the conditions above for every $i$ as a system of linear modular equations.

$$\begin{pmatrix} \alpha_1 h_1(1) & \alpha_2 h_1(2) & \ldots & \alpha_m h_1(m)\\ \alpha_1 h_2(1) & \alpha_2 h_2(2) & \ldots & \alpha_m h_2(m)\\ \vdots & \vdots & \cdots & \vdots\\ \alpha_1 h_n(1) & \alpha_2 h_n(2) & \ldots & \alpha_m h_n(m) \end{pmatrix} \begin{pmatrix} g(1)\\ g(2)\\ \vdots\\ g(n) \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ \vdots\\ 0 \end{pmatrix} \begin{matrix} \mod M\\ \mod M\\ \vdots\\ \mod M \end{matrix}$$ As it is proven in 1, if we sample $t+\lceil\log|G|\rceil$ random solutions of this system of equations we will obtain a generating set of $H^{\perp}$ with probability exponentially close to one $p\geq 1 -1/2^{t}$. Now to sample from this equations write them in matrix form $AX=0 \pmod M$. Here $A$ is a rectangular matrix over the integers modulo $M$ for which an algorithm given in 2 allows to efficiently compute its Smith normal decomposition. The algorithm returns a diagonal matrix $D$ and two invertible matrices $U$, $V$ such that $D=UAV$. Using this formula the system of equations can be written as $DY=0 \pmod M$ with $X=VY$. Now it is possible to randomly compute solutions of $DY=0\pmod M$ using Euclid's algorithm, since this is a system of equations of the form $d_i y_i =0 \pmod M$. Finally, computing $X=VY$ one obtains a random element of the orthogonal group $H^{\perp}$ as desired.

Algorithm for (b):

Since we already know how to compute a generating-set of $H^{\perp}$, it is easy to check if a given element $b$ belongs to $H$. First compute a generating-set $\langle g_1,\ldots, g_s \rangle$ of $H^{\perp}$. Then, by definition, $b$ belongs to $H$ if and only if $\chi_{b}(g_i)=1$ for all generators of $H^{\perp}$. Since there are a O(polylog($|G|$)) number of them and this can be done efficiently using modular arithmetic we are done.