Complexité des tests d'adhésion pour les groupes abéliens finis

Considérez le problème de test d'appartenance au sous-groupe abelian suivant .

Contributions:

Un groupe abélien fini $G=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m}$ avec arbitrairement grand . $d_i$

Un générateur de jeu d'un sous - groupe . $\lbrace h_1,\ldots,h_n\rbrace$ $H\subset G$

Un élément . $b\in G$

Sortie: 'oui' si et 'non' ailleurs '. $b\in H$

Question: Ce problème peut-il être résolu efficacement dans un ordinateur classique? Je considère un algorithme efficace s'il utilise des ressources de temps et de mémoire au sens habituel des machines de Turing classiques. Notez que nous pouvons supposer pour un sous - groupe . La taille d' entrée de ce problème est $O(\text{polylog}|G|)$ $n= O(\log|G|)$ $H$ $\lceil \log|G|\rceil$ .

Un peu de motivation . Intuitivement, il semble que le problème puisse être abordé avec des algorithmes pour résoudre des systèmes linéaires de congruences ou des équations diophantiennes linéaires (lire ci-dessous). Cependant, il semble qu'il existe différentes notions d'efficacité de calcul utilisées dans le contexte des calculs avec des nombres entiers, telles que: temps fortement versus faiblement polynomial, complexité algébrique versus bit. Je ne suis pas un expert de ces définitions et je ne trouve pas de référence qui tranche clairement cette question.

Mise à jour: la réponse au problème est "oui".

Dans une réponse tardive, j'ai proposé une méthode basée sur les formes normales de Smith qui est efficace pour tout groupe avec la forme prescrite.

Une réponse de Blondin montre que dans le cas particulier où tous les sont de la forme et sont de "minuscules entiers" alors le problème appartient à . Les petits entiers sont exponentiellement petits avec la taille d'entrée: . $d_i$ $d_i= N_i^{e_i}$ $N_i, e_i$ $\text{NC}^3\subset \text{P}$ $O(\log\log|A|)$

Dans ma réponse, j'ai utilisé des "sous-groupes orthogonaux" pour résoudre ce problème, mais je pense que ce n'est pas nécessaire. Je vais essayer de fournir une réponse plus directe à l'avenir en fonction d'une méthode de formulaires Echelon que je lis.

Quelques approches possibles

Le problème est étroitement lié à la résolution d'un système linéaire de congruences et / ou d'équations diophantiennes linéaires. Je résume brièvement ces liens par souci d’achèvement.

Prenez pour être la matrice dont les colonnes sont les éléments du groupe électrogène . Le système d'équations suivant $A$ $\lbrace h_1, \ldots, h_n \rbrace$

A x^{T} = (\begin{matrix} h_{1} (1) & h_{2} (1) & \dots & h_{n} (1) \\ h_{1} (2) & h_{2} (2) & \dots & h_{n} (2) \\ ⋮ & ⋮ & \dots & ⋮ \\ h_{1} (m) & h_{2} (m) & \dots & h_{n} (m) \end{matrix}) (\begin{matrix} x (1) \\ x (2) \\ ⋮ \\ x (n) \end{matrix}) = (\begin{matrix} b (1) \\ b (2) \\ ⋮ \\ b (m) \end{matrix}) \begin{matrix} \mod d_{1} \\ \mod d_{2} \\ ⋮ \\ \mod d_{m} \end{matrix}

$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}$

a une solution si et seulement si . $b\in H$

Si tous les facteurs cycliques ont la même dimension il existe un algorithme basé sur les formes normales de Smith qui résout le problème en temps polynomial. Dans ce cas, un algorithme efficace de [1] trouve la forme normale de Smith de : il renvoie une matrice diagonale et deux matrices inversibles et telles que . Cela a réduit le problème de la résolution du système système équivalent avec la diagonaleNous pouvons décider efficacement si le système a une solution en utilisant l'algorithme euclidien. $d=d_i$ $A$ $D$ $U$ $V$ $D=UAV$ $DY=Ub \mod d$ $D$

L'exemple ci-dessus suggère que le problème peut être résolu efficacement en utilisant des techniques similaires dans le cas général. Nous pouvons essayer de résoudre le système en faisant des opérations modulaires, ou en transformant le système en un plus grand système d'équations diophantiennes linéaires. Voici quelques techniques possibles pour aborder le problème auquel je peux penser:

Le calcul des Smith formes normales de . $A$
Le calcul de la ligne Echelon forme d' . $A$
Élimination gaussienne entière.

ds.algorithms time-complexity matrices nt.number-theory gr.group-theory Juan Bermejo Vega
la source

simultanément posté sur MO: mathoverflow.net/questions/81300/…

Suresh Venkat

Il semble que vous ayez transposé cette question simultanément . Bien que cela ne nous dérange pas qu'une question soit republiée , notre politique de site consiste à autoriser une nouvelle publication uniquement après un délai suffisant et que vous n'avez pas obtenu la réponse souhaitée ailleurs, car le crossposting simultané reproduit l'effort et fracture la discussion. Vous pouvez signaler cette question pour fermeture maintenant, puis la redéfinir pour ouverture si nécessaire après avoir résumé les discussions pertinentes d'autres sites.

Suresh Venkat

Fermé à la demande de l'affiche originale (en raison de la duplication sur MO).

Dave Clarke

J'ai posté une réponse avant la fermeture du post. À mon avis, la question est mieux adaptée ici que sur le mathoverflow car elle a été largement étudiée dans la littérature sur la théorie de la complexité.

Michael Blondin

rouvert à la demande du PO; se concentrer sur la complexité en fait le bon choix pour ici.

Suresh Venkat

Réponses:

Vérifier si (où sont des vecteurs selon les observations de la OP) est équivalente à vérifier s'il y a une solution à ce système: $b \in \langle h_1, \ldots, h_n\rangle$ $h_i$

(\begin{matrix} h_{1} (1) & \dots & h_{n} (1) & d_{1}^{e_{1}} & 0 & \dots & 0 \\ ⋮ & ⋱ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ h_{1} (m) & \dots & h_{n} (m) & 0 & 0 & \dots & d_{m}^{e_{N}} \end{matrix}) (\begin{matrix} x (1) \\ ⋮ \\ x (n) \\ y (1) \\ ⋮ \\ y (m) \end{matrix}) \equiv (\begin{matrix} b (1) \\ ⋮ \\ b (m) \end{matrix})

$\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}$

$e_1, \ldots, e_N$ $d_1, \ldots, d_n$

$\text{NC}^3$ $\text{NC}^3$ $\text{NC}^1$

[1] Pierre McKenzie et Stephen A. Cook. La complexité parallèle des problèmes des groupes de permutation abéliens. 1987.

[2] Pierre McKenzie. Groupes de complexité et de permutation parallèles. 1984.

[3] V. Arvind et TC Vijayaraghavan. Classification des problèmes sur les congruences linéaires et les groupes de permutation abéliens à l'aide des classes de comptage des espaces de journalisation. 2010.

Michael Blondin
la source

Z_{N}^{*}

$Z_N^*$

b

$b$

⟨ a ⟩

$\langle a \rangle$

b = a^{i} \mod φ (N)

$b=a^i\mod \varphi(N)$

En fait, c'est pour tout groupe de permutation abélien .

Michael Blondin

Je vais jeter un œil à ces papiers et essayer de tout organiser un peu. Merci.

Juan Bermejo Vega

Pourriez-vous fournir plus de détails sur l'encodage de l'entrée? De cette façon, je pourrais peut-être améliorer ma réponse.

Michael Blondin

A = Z_{d_{1}} \times Z_{d_{1}} \dots \times Z_{d_{N}}

$A=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_N}$

(g_{1}, \dots, g_{n})

$(g_1,\ldots,g_n)$

n := ⌈ l o g_{2} | A | ⌉

$n:= \lceil log_2 |A|\rceil$

Après un certain temps, j'ai réussi à trouver un algorithme peut-être pas optimal mais simple qui prouve que la complexité du problème est polynomiale.

Algorithme

$H^{\perp}$ $H$

$b$ $H^{\perp}$

$b$ $H^\perp$ $h\in H$

Une analyse

$H^{\perp}$ $G$

H^{⊥} := {g \in G : χ_{g} (h) = 1 \forall h \in H}

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

$H^{\perp}$ $G$
$H^{\perp^\perp}=H$

Algorithme pour (a) :

$g$ $H^{\perp}$ $\chi_{g}(h)=1$ $h\in H$ $\chi_{b}(h_i)=1$ $H$

\begin{array}{rcl} \exp {2 π i (\frac{g (1) h_{i} (1)}{d_{1}} + \dots + \frac{g (m) h_{i} (m)}{d_{m}})} = 1 \end{array}

$\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}$

M := lcm (N_{1}, \dots, N_{d})

$M:= \text{lcm}(N_1,\ldots,N_d)$

α_{i} := M / d_{i}

$\alpha_i:=M/d_i$

i

$i$

(\begin{matrix} α_{1} h_{1} (1) & α_{2} h_{1} (2) & \dots & α_{m} h_{1} (m) \\ α_{1} h_{2} (1) & α_{2} h_{2} (2) & \dots & α_{m} h_{2} (m) \\ ⋮ & ⋮ & \dots & ⋮ \\ α_{1} h_{n} (1) & α_{2} h_{n} (2) & \dots & α_{m} h_{n} (m) \end{matrix}) (\begin{matrix} g (1) \\ g (2) \\ ⋮ \\ g (n) \end{matrix}) = (\begin{matrix} 0 \\ 0 \\ ⋮ \\ 0 \end{matrix}) \begin{matrix} \mod M \\ \mod M \\ ⋮ \\ \mod M \end{matrix}

$\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}$

t + ⌈ \log | G | ⌉

$t+\lceil\log|G|\rceil$

H^{⊥}

$H^{\perp}$

p \geq 1 - 1 / 2^{t}

$p\geq 1 -1/2^{t}$

A X = 0 (\mod M)

$AX=0 \pmod M$

A

$A$

M

$M$

D

$D$

U

$U$

V

$V$

D = U A V

$D=UAV$

D Y = 0 (\mod M)

$DY=0 \pmod M$

X = V Y

$X=VY$

D Y = 0 (\mod M)

$DY=0\pmod M$

d_{i} y_{i} = 0 (\mod M)

$d_i y_i =0 \pmod M$

X = V Y

$X=VY$

H^{⊥}

$H^{\perp}$

Algorithme pour (b) :

$H^{\perp}$ $b$ $H$ $\langle g_1,\ldots, g_s \rangle$ $H^{\perp}$ $b$ $H$ $\chi_{b}(g_i)=1$ $H^{\perp}$ $|G|$ )) nombre d'entre eux et cela peut être fait efficacement en utilisant l'arithmétique modulaire, nous avons terminé.

Juan Bermejo Vega
la source

il est bon d'ajouter votre propre réponse si vous avez fait des découvertes entre-temps. Cependant, il semble que vous ayez besoin de faire plus d'investigation (sur la base de votre commentaire) avant de décider quelle réponse accepter.

Suresh Venkat

Merci. Je voudrais poursuivre la discussion pour voir si nous mettons tout dans une seule image. De plus, je pense qu'il pourrait y avoir un algorithme plus pratique qui pourrait apparaître.

Juan Bermejo Vega