Complexidade do problema de interseção de coset

17

Dado o grupo de simetria e dois subgrupos e , mantém?SnG,HSnπSnGπH=

Tanto quanto eu sei, o problema é conhecido como o problema de interseção de coset. Eu estou querendo saber qual é a complexidade? Em particular, esse problema é conhecido por estar no coAM?

Além disso, se é restrito a ser abeliano, qual é a complexidade?H

maomao
fonte
2
Como os dois grupos são representados como entrada?
Emil Jeřábek apoia Monica
11
por convenção, eles são dados por conjuntos de geradores.
maomao 25/09/14
11
O problema de interseção de coset é tipicamente formulado de maneira oposta: a resposta é sim se eles se cruzam. É esta versão do problema que é em . NPcoAM
Joshua Grochow 26/09
Uma observação interessante, que invalida nenhuma das opções acima: isomorfismo de grafos, interseção de coset e isomorfismo de cordas, foram todos objeto de um novo resultado de Babai, descrito pela primeira vez em um seminário há alguns dias. Ainda não há publicação, mas parece que agora existe um algoritmo quase-polinomial para todos eles.
Perry

Respostas:

11

Tempo moderadamente exponencial e (para o oposto do problema, como indicado: a interseção de coset é normalmente considerada como tendo uma resposta "sim" se os cosets se cruzarem, ao contrário de como é declarado no OQ.)coAM

Luks 1999 ( cópia do autor livre ) forneceu um algoritmo de tempo, enquanto Babai (veja sua tese de doutorado em 1983, também Babai-Kantor-Luks FOCS 1983 e uma versão em diário) deu uma 2 ˜ O ( 2O(n)algoritmo time, que continua sendo o mais conhecido até o momento. Desde gráfico isomorfismo reduz a intersecção coset quadrática de tamanho, melhorando isso a2 ~ S (n 1 / 4 - ε )iria melhorar o estado da arte para isomorfismo gráfico.2O~(n)2O~(n1/4ϵ)

Joshua Grochow
fonte
9

Considere o complemento, ou seja, onde você será solicitado a testar se . Como já apontado no esta resposta , testando se g g 1 , ... , g k é em NC P [1]. Então você pode adivinhar g , h S n e testar em tempo polinomial se g G , h H e g π = h . Isto produz um NPGπHgg1,,gkNCPg,hSngGhHgπ=hNPlimite superior e, portanto, seu problema está no .coNP

Edit : É mostrado em [2, Thm. 15] que o problema de interseção do coseto está em . Como observado aqui , p. 7, o problema de interseção de coset não é, portanto, NP completo, a menos que a hierarquia polinomial de tempo entre em colapso. Além disso, é observado aqui , p. 6, que Luks demonstrou que o problema está em P quando H é solucionável, o que inclui o caso de H abelian.NPcoAMPHH

[1]  L. Babai, EM Luks e A. Seress. Grupos de permutação em NC . Proc. 19o simpósio anual da ACM sobre Teoria da Computação, pp. 409-420, 1987.

[2] L. Babai, S. Moran. Jogos Arthur-Merlin: Um sistema de provas aleatórias e uma hierarquia de classes de complexidade . Journal of Computer and System Sciences, vol. 36, edição 2, pp. 254-276, 1988.

Michael Blondin
fonte
muito obrigado pela resposta. Para o caso H é um subgrupo normal, é claro. No entanto, se H é apenas abeliano, não está realmente claro para mim. Does ainda mantêm? (desculpe por minha estupidez ...)GH=<st:sS,tT>
maomao
Meu mal, meu cérebro misturou "normal" e "solucionável" por um momento. Eu sinto Muito. Eu editei a resposta, espero que responda à sua pergunta.
Michael Blondin
11
Quando H é um subgrupo normal de G, o problema de interseção de coset é muito mais fácil: reduz-se apenas ao problema de associação (é em G). π
Joshua Grochow
Certo, obrigada. Essa parte da minha resposta é praticamente inútil então.
Michael Blondin
Eu removi o parágrafo, era apenas confuso.
Michael Blondin