Complexité du problème d'intersection coset

Étant donné le groupe de symétrie et deux sous-groupes et , ? G , H ≤ S n π ∈ S n G π ∩ H = $S_n$$G, H\leq S_n$$\pi\in S_n$$G\pi\cap H=\emptyset$

Pour autant que je sache, le problème est connu sous le nom de problème d'intersection de coset. Je me demande quelle est la complexité? En particulier, ce problème est-il connu dans COAM?

De plus, si se limite à être abélien, que devient la complexité?$H$

Temps modérément exponentiel et (pour l'opposé du problème comme indiqué: l'intersection de coset est généralement considérée comme ayant une réponse «oui» si les cosets se croisent, contrairement à la façon dont elle est indiquée dans l'OQ.)$\mathsf{coAM}$

Luks 1999 ( copie gratuite de l'auteur ) a donné un algorithme à temps , tandis que Babai (voir sa thèse de doctorat de 1983, également Babai-Kantor-Luks FOCS 1983 , et une version de journal à paraître) a donné un 2 ˜ O ( $2^{O(n)}$algorithme de temps, qui reste le plus connu à ce jour. Depuis graphique réduit isomorphisme àintersection coset quadratique moyenne,améliorationce à2 ~ O (n 1 / 4 - ε )améliorerait l'état de l'art graphique pour isomorphisme.$2^{\tilde{O}(\sqrt{n})}$$2^{\tilde{O}(n^{1/4-\epsilon})}$

Considérons le complément, c'est-à-dire où l'on vous demande de tester si . Comme je l' ai souligné dans cette réponse , vérifier si g ∈ ⟨ g 1 , ... , g k ⟩ est - à NC ⊆ P [1]. Vous pouvez donc deviner g , h ∈ S n et tester en temps polynomial si g ∈ G , h ∈ H et g π = h . Cela donne un $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}$borne supérieure et, par conséquent, votre problème est en .$\text{coNP}$

Edit : Il est montré dans [2, Thm. 15] que le problème d'intersection coset est dans . Comme indiqué ici , p. 7, le problème d'intersection de coset n'est donc pas NP-complet, à moins que la hiérarchie temporelle polynomiale ne s'effondre. De plus, il est noté ici , p. 6, qu'il a été démontré par Luks que le problème est dans P quand H est résoluble, ce qui inclut le cas de H abelian.$\text{NP} \cap \text{coAM}$$\text{P}$$H$$H$

[1]  L. Babai, EM Luks et A. Seress. Groupes de permutation en NC . Proc. 19e symposium annuel de l'ACM sur la théorie de l'informatique, pp. 409-420, 1987.

[2] L. Babai, S. Moran. Jeux Arthur-Merlin: un système de preuve aléatoire et une hiérarchie de classes de complexité . Journal of Computer and System Sciences, vol. 36, numéro 2, pp. 254-276, 1988.