Złożoność problemu przecięcia cosetów

Biorąc pod uwagę grupę symetrii i dwie podgrupy i , czy ?$S_n$$G, H\leq S_n$$\pi\in S_n$$G\pi\cap H=\emptyset$

O ile mi wiadomo, problem ten znany jest jako problem przecięcia cosetów. Zastanawiam się, jaka jest złożoność? W szczególności, czy wiadomo, że ten problem występuje w CoAM?

Co więcej, jeśli jest ograniczone do abelowego, na czym polega złożoność?$H$

Czas umiarkowanie wykładniczy i (w przeciwieństwie do tego, co stwierdzono: Przecięcie Coset zwykle uważa się za posiadające odpowiedź „tak”, jeśli przecinają się Cosety, w przeciwieństwie do tego, jak podano w OQ.)$\mathsf{coAM}$

Luks 1999 ( darmowy egzemplarz autora ) podał algorytm , podczas gdy Babai (patrz jego rozprawa doktorska z 1983 r., Także Babai-Kantor-Luks FOCS 1983 i pojawiająca się wersja czasopisma) dali 2 ˜ O ( $2^{O(n)}$algorytm czasu, który pozostaje najlepiej znanym do tej pory. Ponieważ izomorfizm grafu sprowadza się do kwadratu przecięcia cosetów, poprawiając to do$2^{\tilde{O}(\sqrt{n})}$by polepszyć stan techniki dla wykresu izomorfizmie.$2^{\tilde{O}(n^{1/4-\epsilon})}$

Zastanów się nad dopełnieniem, tzn. Gdy jesteś proszony o sprawdzenie, czy . Jak wskazano w tej odpowiedzi , sprawdzając, czy g ∈ ⟨ g 1 , ... , g k ⟩ znajduje się w NC ⊆ P [1]. Możesz więc zgadnąć g , h ∈ S n i sprawdzić w czasie wielomianowym, czy g ∈ $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$ , i g π = h . Daje to $h \in H$$g \pi = h$$\text{NP}$górna granica, a zatem twój problem dotyczy .$\text{coNP}$

Edycja : Pokazano w [2, Thm. 15], że problem przecięcia cosetu występuje w CoAM . Jak wspomniano tutaj , str. 7, problem przecięcia cosetu nie jest zatem NP-zupełny, chyba że załamie się wielomianowa hierarchia czasu. Ponadto odnotowano tutaj , str. 6, że Luks wykazał, że problem występuje w P, gdy H można rozwiązać, co obejmuje przypadek H abeliana.$\text{NP} \cap \text{coAM}$$\text{P}$$H$$H$

[1]  L. Babai, EM Luks i A. Seress. Grupy permutacyjne w NC . Proc. 19. doroczne sympozjum ACM na temat teorii obliczeń, s. 409–420, 1987.

[2] L. Babai, S. Moran. Gry Arthur-Merlin: Losowy system dowodowy i hierarchia klas złożoności . Journal of Computer and System Sciences, tom. 36, wydanie 2, str. 254–276, 1988.