Komplexität von Mitgliedschaftstests für endliche abelsche Gruppen

12

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

Eingänge:

  1. Eine endliche abelsche Gruppe G=Zd1×Zd1×Zdm mit beliebig großem di .

  2. Ein Generatorsatz {h1,,hn} eine Untergruppe HG .

  3. Ein Element bG .

Ausgang: ‚Ja‘ , wenn bH 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(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|)Hlog|G|

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 N habendidi=Niei sind "kleine ganze Zahlen"dann gehört das Problem zu NC 3P . Winzige Ganzzahlen sind exponentiell klein mit der Eingabegröße: O ( log log | A | ) .Ni,eiNC3PO(loglog|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 GleichungssystemA{h1,,hn}

AxT=(h1(1)h2(1)hn(1)h1(2)h2(2)hn(2)h1(m)h2(m)hn(m))(x(1)x(2)x(n))=(b(1)b(2)b(m))modd1modd2moddm

wenn eine Lösung hat , und nur wenn .bH

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 bd=diADUVD=UAV mit D- Diagonale. Wir können effizient entscheiden, ob das System eine Lösung mit dem euklidischen Algorithmus hat.DY=UbmoddD

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.
Juan Bermejo Vega
quelle
1
gleichzeitig auf MO crossposted
Suresh Venkat
2
Es scheint, dass Sie diese Frage gleichzeitig gekreuzt haben . Während wir nicht eine Frage denkt, die reposted unsere, Standortrichtlinie ist ein repost zu ermöglichen erst nach ausreichender Zeit vergangen ist , und Sie haben die gewünschte Antwort an anderer Stelle nicht erhalten, weil die gleichzeitige Crossposting dupliziert Diskussion Aufwand und Frakturen. Sie können diese Frage zum Schließen markieren und sie dann zum Öffnen neu markieren, nachdem Sie die relevanten Diskussionen auf anderen Websites zusammengefasst haben.
Suresh Venkat
1
Auf Wunsch des Originalplakats geschlossen (wegen Vervielfältigung auf MO).
Dave Clarke
1
Ich habe eine Antwort gepostet, bevor der Beitrag geschlossen wurde. Meiner Meinung nach ist die Frage hier besser geeignet als für Mathoverflow, da sie in der Literatur zur Komplexitätstheorie ausführlich untersucht wurde.
Michael Blondin
1
auf OP-Antrag wieder geöffnet; Die Fokussierung auf Komplexität macht es hier passend.
Suresh Venkat

Antworten:

10

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 0bh1,,hnhi

(h1(1)hn(1)d1e100h1(m)hn(m)00dmeN)(x(1)x(n)y(1)y(m))(b(1)b(m))

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 , ,e1,,eN winzig sind.d1,,dn

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 .NC3NC3NC1

[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.

Michael Blondin
quelle
Danke, leider habe ich bis Montag keinen Zugang zu diesen Papieren. Es überrascht mich, dass dies für jede abelsche Gruppe funktioniert. Für , die abelian ist, ob die Bestimmung b gehört eine beinhaltet entscheiden , ob b = eine iZNba hat eine Lösung. Ich sehe hier zwei Probleme: 1) Klassischerweise ist es schwierig, die Euler-Totientenfunktion zu berechnen. 2) Es ist die Entscheidungsversion eines diskreten Logarithmus. Das Problem reduziert sich auf die Lösung modularer Gleichungen, wenn die zyklische Zerlegung gegeben ist. Wie umgehen Sie dieses Problem? Vermisse ich hier etwas Wichtiges? b=aimodφ(N)
Juan Bermejo Vega
Eigentlich ist es für jede abelsche Permutationsgruppe .
Michael Blondin
Ich werde mir diese Papiere ansehen und versuchen, alles ein bisschen zu organisieren. Vielen Dank.
Juan Bermejo Vega
Könnten Sie weitere Details zur Kodierung der Eingabe angeben? Auf diese Weise kann ich möglicherweise meine Antwort verbessern.
Michael Blondin
Die Gruppenzerlegung als Eingabe (dies wäre eine Zeichenfolge mit mehreren Zahlen und der Länge, die ich schätze). Dann hat jedes Element der Gruppe die Form ( g 1 , ... , g n ) und kann durch ein Tupel von Zahlen dargestellt werden. Zum Speichern benötigen Sie n : = l o g 2 | A | Bits. Beantwortet das das? A=Zd1×Zd1×ZdN(g1,,gn)n:=log2|A|
Juan Bermejo Vega
4

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 HHH .

(b) Prüfen Sie, ob das Element orthogonal zu H ist oder nicht .bH

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 .bHhH


Analyse

HG

H:={gG:χg(h)=1hH}
  1. HG
  2. H=H

Algorithmus für (a) :

gHχg(h)=1hH, but, by linearity it is enough to show χb(hi)=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

exp{2πi(g(1)hi(1)d1++g(m)hi(m)dm)}=1
To solve these equations, compute M:=lcm(N1,,Nd) using the Euclidean algorithm and the numbers αi:=M/di. We can re-write the conditions above for every i as a system of linear modular equations.

(α1h1(1)α2h1(2)αmh1(m)α1h2(1)α2h2(2)αmh2(m)α1hn(1)α2hn(2)αmhn(m))(g(1)g(2)g(n))=(000)modMmodMmodM
As it is proven in 1, if we sample t+log|G| random solutions of this system of equations we will obtain a generating set of H with probability exponentially close to one p11/2t. Now to sample from this equations write them in matrix form AX=0(modM). 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(modM) with X=VY. Now it is possible to randomly compute solutions of DY=0(modM) using Euclid's algorithm, since this is a system of equations of the form diyi=0(modM). Finally, computing X=VY one obtains a random element of the orthogonal group H as desired.

Algorithm for (b):

Since we already know how to compute a generating-set of H, it is easy to check if a given element b belongs to H. First compute a generating-set g1,,gs of H. Then, by definition, b belongs to H if and only if χb(gi)=1 for all generators of H. Since there are a O(polylog(|G|)) number of them and this can be done efficiently using modular arithmetic we are done.

Juan Bermejo Vega
quelle
1
it's fine to add your own answer if you've made discoveries in the mean time. However, it seems like you need to do some more investigation (based on your comment) before you decide which answer to accept.
Suresh Venkat
Thanks. I would like to keep the discussion further to see if we put everything into one picture. Also, I think there could be a more practical algorithm that could pop-up.
Juan Bermejo Vega