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?

cc.complexity-theory reference-request quantum-computing graph-isomorphism 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

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 . $S_n$ $Aut(G)$

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

Reduktion zum HSP über . Wenn wir wissen wollen, ob zwei Graphen und auf Ecken isomorph sind, betrachten wir den Graphen der die disjunkte Vereinigung von und auf Ecken ist. Lassen wirken auf der Vertices durch Vertauschen mit für . Entweder $S_n \wr \mathbb{Z}/2\mathbb{Z}$ $G$ $H$ $n$ $K$ $G$ $H$ $2n$ $\mathbb{Z}/2\mathbb{Z}$ $i$ $n+i$ $i=1,...,n$ oder . Nach wie vor sei $Aut(K) = Aut(G) \times Aut(H)$ $Aut(K) = (Aut(G) \times Aut(H)) semidirect \mathbb{Z}/2\mathbb{Z}$ wobei nun ein Element von , daswie beschriebenauf einwirkt. Die versteckte Untergruppe zugeordnet genau , wie in der vorherige Reduktion. Wenn wir dieses HSP lösen, erhalten wir einen Generator für . Es ist dann einfach zu überprüfen, ob der Generator ein Element enthält, das die Kopie von mit der Kopie von vertauscht $f(x)=x(K)$ $x$ $S_n \wr \mathbb{Z}/2\mathbb{Z}$ $K$ $f$ $Aut(K)$ $Aut(K)$ $G$ $H$ (hat nichttriviale Komponente). $K$ $\mathbb{Z}/2\mathbb{Z}$

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

Graph Isomorphism und versteckte Untergruppen

Antworten: