Grafik Isomorfisme dan subkelompok tersembunyi

23

Saya mencoba memahami hubungan antara isomorfisme grafik dan masalah subkelompok tersembunyi. Apakah ada referensi yang bagus untuk ini?

cc.complexity-theory reference-request quantum-computing graph-isomorphism Suresh Venkat
sumber

2

Tssk, kami tidak hanya perlu menyembuhkan penyakit GI Anda, tetapi juga semua pembaca miskin pertanyaan Anda yang juga terinfeksi! (Ini bercanda, saya agak rentan terhadap penyakit GI juga.)

András Salamon

1

terlalu benar. Saya harus menjauh dari Dave Bacon sekarang :)

Suresh Venkat

2

FYI, makalah yang relatif baru berikut saya pikir meletakkan paku di peti mati pada "algoritma saringan kuantum" untuk GI, yang mencakup banyak upaya sejauh ini (dan tidak disebutkan dalam posting blog Dave Bacon): dx.doi.org/ 10.1137 / 080724101 . Makalah ini berat pada teori representasi, tetapi intro tidak, dan merupakan bacaan yang cukup bagus.

Joshua Grochow

20

Referensi dapat ditemukan dalam jawaban martinschwarz, tetapi di sini adalah ringkasan dari beberapa pengurangan.

Grup simetris bekerja pada grafik n simpul dengan mengijinkan simpul tersebut. Menentukan apakah dua grafik isomorfik adalah polinomial-time ekuivalen dengan penghitungan genset ukuran polinomial untuk . $S_n$ $Aut(G)$

Reduksi ke HSP melalui grup simetris (di mana adalah jumlah variabel dalam grafik). Fungsi adalah di mana adalah permutasi di , dan adalah versi permuted . Kemudian konstan pada cosets dan berbeda pada cosets berbeda (perhatikan bahwa gambar terdiri dari semua grafik isomorfik ke ). Karena subkelompok tersembunyi persis , jika kita bisa menyelesaikan HSP ini maka kita akan memiliki set pembangkit untuk $S_n$ $n$ $f$ $f(p)=p(G)$ $p$ $S_n$ $p(G)$ $G$ $f$ $Aut(G)$ $f$ $G$ $Aut(G)$ $Aut(G)$ , yang kita butuhkan untuk menyelesaikan GI (lihat di atas).

Pengurangan ke HSP melalui . Jika kita ingin tahu apakah dua grafik dan pada simpul adalah isomorfik, perhatikan grafik yang merupakan gabungan tak terpisahkan dari dan pada simpul . Biarkan bekerja pada simpul dengan menukar dengan untuk . Baik atau . Seperti sebelumnya, misalkan mana $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$ $Aut(K) = Aut(G) \times Aut(H)$ $Aut(K) = (Aut(G) \times Aut(H)) semidirect \mathbb{Z}/2\mathbb{Z}$ $f(x)=x(K)$ $x$ sekarang merupakan elemen dari yang bekerja pada seperti dijelaskan. Subkelompok tersembunyi yang terkait dengan persis , seperti pada pengurangan sebelumnya. Jika kami mengatasi HSP ini, kami mendapatkan set pembangkit untuk . Maka mudah untuk memeriksa apakah himpunan pembangkit berisi elemen yang menukar salinan dengan salinan di dalam (memiliki komponen nontrivial ). $S_n \wr \mathbb{Z}/2\mathbb{Z}$ $K$ $f$ $Aut(K)$ $Aut(K)$ $G$ $H$ $K$ $\mathbb{Z}/2\mathbb{Z}$

Joshua Grochow
sumber

17

Anda mungkin ingin membaca posting blog terbaru Dave Bacon di Graph Isomorphism dengan tautan ke literatur.

Martin Schwarz
sumber

14

"Algoritma kuantum untuk masalah aljabar" oleh Andrew Childs dan Wim van Dam arXiv: 0812.0380 adalah makalah survei yang sangat bagus yang berisi intro yang bagus tentang HSP non-Abelian dan hubungannya dengan Graph Isomorphism.

dabacon
sumber

Grafik Isomorfisme dan subkelompok tersembunyi

Jawaban: