Graph Isomorphism und versteckte Untergruppen

23

Ich versuche, die Beziehung zwischen dem Graphisomorphismus und dem Problem der versteckten Untergruppen zu verstehen. Gibt es dafür eine gute Referenz?

Suresh Venkat
quelle
2
Tssk, wir müssen nicht nur Ihre GI-Krankheit heilen, sondern auch alle armen Leser Ihrer Frage, die sich ebenfalls infizieren! (Dies ist im Scherz, ich bin etwas anfällig für GI-Krankheit auch.)
András Salamon
1
zu wahr. Ich muss mich jetzt von Dave Bacon fernhalten :)
Suresh Venkat
2
FYI, die folgende, meiner Meinung nach relativ neue Veröffentlichung, hat die Frage nach "Quantensieb-Algorithmen" für GI, die viele der bisherigen Versuche abdeckt (und in Dave Bacons Blog-Post nicht erwähnt wird), auf den Punkt gebracht : dx.doi.org/ 10.1137 / 080724101 . Die Abhandlung beschäftigt sich intensiv mit Repräsentationstheorie, das Intro jedoch nicht und ist eine ziemlich gute Lektüre.
Joshua Grochow

Antworten:

20

Referenzen finden Sie in martinschwarz 'Antwort, aber hier ist eine Zusammenfassung einiger Reduktionen.

Die symmetrische Gruppe wirkt auf Graphen von n Ecken durch die Eckpunkte Permutieren. Bestimmen , ob zwei Graphen isomorph ist Polynom Zeitäquivalent eines Polynom-size Stromerzeuger zu Rechen A u t ( G ) .SnAut(G)

Reduktion zum HSP über die symmetrische Gruppe (wobei n die Anzahl der Variablen in der Grafik ist). Die Funktion f ist , f ( p ) = p ( G ) , wo p eine Permutation in ist S n , und p ( G ) ist die permutierte Version von G . Dann ist f auf Nebenmengen von A u t ( G ) konstant und auf Nebenmengen unterschiedlich (beachten Sie, dass das Bild von fSnnff(p)=p(G)pSnp(G)GfAut(G)fbesteht aus allen zu ) isomorphen Graphen . Da die versteckte Untergruppe genau A u t ( G ) ist , hätten wir, wenn wir diesen HSP lösen könnten, den Generator für A u t ( G ) , was alles ist, was wir brauchen, um GI zu lösen (siehe oben).GAut(G)Aut(G)

Reduktion zum HSP über . Wenn wir wissen wollen, ob zwei Graphen G und H auf n Ecken isomorph sind, betrachten wir den Graphen K, der die disjunkte Vereinigung von G und H auf 2 n Ecken ist. Lassen Z / 2 Z wirken auf der Vertices durch Vertauschen i mit n + i für i = 1 , . . . , N . Entweder ASnZ/2ZGHnKGH2nZ/2Zichn+ichich=1,...,n oder A u t ( K ) = ( A u t ( G ) x A u t ( H ) ) s e m i d i r e c t Z / 2 Z . Nach wie vor sei f ( xEINut(K)=EINut(G)×EINut(H)EINut(K)=(EINut(G)×EINut(H))semichdichrectZ/2Z wobei x nun ein Element von S nZ / 2 Z ist , daswie beschriebenauf K einwirkt. Die versteckte Untergruppe zugeordnet sind f genau A u t ( K ) , wie in der vorherige Reduktion. Wenn wir dieses HSP lösen, erhalten wir einen Generator für A u t ( K ) . Es ist dann einfach zu überprüfen, ob der Generator ein Element enthält, das die Kopie von G mit der Kopie von H vertauschtf(x)=x(K)xSnZ/2ZKfEINut(K)EINut(K)GH (hat nichttriviale Z / 2 Z- Komponente).KZ/2Z

Joshua Grochow
quelle
17

Vielleicht möchten Sie Dave Bacons neuesten Blog-Beitrag über Graph Isomorphism mit Links zur Literatur lesen .

Martin Schwarz
quelle
14

" Quantenalgorithmen für algebraische Probleme" von Andrew Childs und Wim van Dam arXiv: 0812.0380 ist eine sehr gute Übersicht, die eine gute Einführung in das nicht-abelsche HSP und seine Beziehung zum Graphisomorphismus enthält.

Dabacon
quelle