Kompleksitas masalah persimpangan coset

Dengan diberikannya kelompok simetri dan dua subkelompok , dan , apakah tahan?$S_n$$G, H\leq S_n$$\pi\in S_n$$G\pi\cap H=\emptyset$

Sejauh yang saya tahu, masalahnya dikenal sebagai masalah persimpangan coset. Saya bertanya-tanya apa kerumitannya? Secara khusus, apakah masalah ini diketahui berada dalam COAM?

Terlebih lagi, jika dibatasi menjadi abelian, seperti apa kompleksitasnya?$H$

Waktu yang cukup eksponensial dan (untuk kebalikan dari masalah seperti yang dinyatakan: Coset Intersection biasanya dianggap memiliki jawaban "ya" jika cosets berpotongan, kebalikan dari yang dinyatakan dalam OQ.)$\mathsf{coAM}$

Luks 1999 ( salinan penulis gratis ) memberikan algoritma -waktu, sementara Babai (lihat tesis Ph.D 1983-nya, juga Babai-Kantor-Luks FOCS 1983 , dan versi jurnal yang akan muncul) memberikan 2 ˜ O ( $2^{O(n)}$algoritma waktu, yang tetap paling dikenal hingga saat ini. Sejak grafik isomorfisma mengurangi ke persimpangan koset kuadrat berukuran, meningkatkan ini untuk2 ~ O (n 1 / 4 - ε )akan meningkatkan keadaan seni untuk grafik isomorfisma.$2^{\tilde{O}(\sqrt{n})}$$2^{\tilde{O}(n^{1/4-\epsilon})}$

Pertimbangkan komplemen, yaitu di mana Anda diminta untuk menguji apakah . Seperti yang saya tunjukkan dalam jawaban ini , menguji apakah g ∈ ⟨ g 1 , ... , g k ⟩ yaitu di NC ⊆ P [1]. Jadi Anda dapat menebak g , h ∈ S n, dan menguji dalam waktu polinomial apakah g ∈ G , h ∈ H, dan g π = h . Ini menghasilkan $G \pi \cap H \not= \emptyset$$g \in \langle g_1, \ldots, g_k\rangle$$\text{NC} \subseteq \text{P}$$g, h \in S_n$$g \in G$$h \in H$$g \pi = h$$\text{NP}$batas atas dan, oleh karena itu, masalah Anda ada dalam .$\text{coNP}$

Sunting : Ditampilkan di [2, Thm. 15] bahwa masalah persimpangan coset adalah dalam . Seperti disebutkan di sini , hal. 7, masalah persimpangan coset karena itu bukan NP-lengkap, kecuali hirarki waktu polinomial runtuh. Selain itu, tercantum di sini , hal. 6, yang ditunjukkan oleh Luks bahwa masalahnya ada di P ketika H dapat dipecahkan, yang mencakup kasus $\text{NP} \cap \text{coAM}$$\text{P}$$H$$H$ abelian.

[1]  L. Babai, EM Luks & A. Seress. Grup permutasi di NC . Proc Simposium ACM ke 19 tentang Teori komputasi, hal. 409-420, 1987.

[2] L. Babai, S. Moran. Permainan Arthur-Merlin: Sistem bukti acak, dan hierarki kelas kompleksitas . Jurnal Ilmu Komputer dan Sistem, vol. 36, edisi 2, hlm. 254-276, 1988.