O isomorfismo do grupo abeliano está em

Um algoritmo de tempo de execução para isomorfismo de grupo abeliano é fácil de ver. Mais tarde, trabalhando nesse problema em 2003, o Vikas aprimorou o resultado do tempo de execução de O ( n 2 ) para O ( n log n ) . Em 2007, Kavitha mostrou que o isomorfismo do grupo abeliano pode ser feito em tempo linear, isto é, tempo O ( n ) .$O(n^2)$$O(n^2)$$O(n \log n)$$O(n)$

Eu sei que o isomorfismo do grupo abeliano quando os grupos são dados por representação de tabela está em . Existe algum trabalho ou artigo de pesquisa que mostre que está em A C 0 ? Tentei pesquisar no google, mas obtive apenas o resultado que está no T C 0 .$\mathsf{TC^0}$$\mathsf{AC^0}$$\mathsf{TC^0}$

Pergunta: Isomorfismo do grupo abeliano (grupos dados na representação de tabela) em $\mathsf{AC^0}$

Ao contrário do que é afirmado na pergunta, não se sabe que o isomorfismo do grupo abeliano esteja em . Escusado será dizer que isso também significa que não é conhecido por estar em A C 0 .$\mathrm{TC^0}$$\mathrm{AC^0}$

O que se sabe é a seguinte observação de [1]. Deixe denotam o seguinte problema: dada uma tabela de multiplicação de um grupo abeliano ( A , ⋅ ) , os elementos de uma , b ∈ A , e m em unária, determinar se b = um m . O teorema da estrutura para grupos abelianos finitos implica facilmente que, se A , B são dois desses grupos de tamanho n , então$\mathrm{pow}$$(A,{\cdot})$$a,b\in A$$m$$b=a^m$$A,B$$n$

Como podemos contar conjuntos de tamanho polinomial em , obtemos$\mathrm{TC^0}$

Proposição 1: isomorfismo grupo Abeliano é calculável no .$\mathrm{TC^0(pow)}$

Agora, é claramente calculável em L, e como mostrado em [2], também na classe SS. Portanto,$\mathrm{pow}$

Corolário 2: O isomorfismo do grupo abeliano é computável em e em T C 0 ( F O L L ) .$\mathrm{L}$$\mathrm{TC^0(FOLL)}$

Não se sabe se é calculável no t C 0 .$\mathrm{pow}$$\mathrm{TC^0}$

Parece que o Corolário 2 é o resultado mais conhecido quando se trata de classes de circuito usuais, de "tamanho polinomial". No entanto, observei que o problema está na versão quase - polinomial de :$\mathrm{AC^0}$

Proposição 3: O isomorfismo do grupo abeliano é computável por uma sequência uniforme de circuitos booleanos de profundidade constante de tamanho quase-polinomial; mais especificamente, está em .$\Sigma_2\text-\mathrm{TIME}\bigl((\log n)^2\bigr)$

(Isso se traduz em uma família uniforme de circuitos de profundidade 3 do tamanho , em que as disjunções inferiores possuem apenas fan-in O ( ( log n ) 2 ) ; isso é freqüentemente chamado de “profundidade 2 $2^{O((\log n)^2)}$$O\bigl((\log n)^2\bigr)$ ".)$2\frac12$

A proposição 3 é novamente uma conseqüência do teorema da estrutura para grupos abelianos finitos: qualquer grupo pode ser escrito como uma soma direta de subgrupos cíclicos ; portanto, os grupos A e B são isomórficos se puderem ser escritos como somas diretas de subgrupos cíclicos com ordens correspondentes: ou seja, se | Um | = | B | = n , então A ≃ B se$O(\log n)$$A$$B$$|A|=|B|=n$$A\simeq B$

existe

• uma sequência de k ≤ log n números inteiros m i ≤ $\{m_i:i<k\}$$k\le\log n$$m_i\le n$

• seqüências e { b i : i < k } ⊆ $\{a_i:i<k\}\subseteq A$$\{b_i:i<k\}\subseteq B$

de tal modo que

• $\prod_{i<k}m_i=n$

• e b m i i = 1 para cada i < $a_i^{m_i}=1$$b_i^{m_i}=1$$i<k$

• para todas as seqüências de números inteiros 0 ≤ r i < m i , nem todos zero:$\{r_i:i<k\}$$0\le r_i<m_i$

  e Π i < k b r i i ≠ $\prod_{i<k}a_i^{r_i}\ne1$$\prod_{i<k}b_i^{r_i}\ne 1$

Os dois quantificadores principais são destacados. Para garantir que os limites declarados não sejam excedidos, precisamos mostrar que as identidades podem ser verificadas em N T I M E ( ( log n ) 2 ) . Isso pode ser feito adivinhando e verificando sucessivamente os valores dos produtos parciais ∏ i < l a r i i para l = 0 , … , k ; além disso, para cada $\prod_{i<k}a_i^{r_i}=1$$\mathrm{NTIME}\bigl((\log n)^2\bigr)$$\prod_{i<l}a_i^{r_i}$$l=0,\dots,k$$i$, Que de modo semelhante adivinhar e verificar os resultados parciais do cálculo de um r i i por quadratura repetido. No total, isto faz com que ó ( Σ i log r i ) ⊆ S ( Σ i log m i ) ⊆ S ( log n ) suposições, cada um dos quais leva O ( log n ) de tempo para verificar.$O(\log r_i)$$a_i^{r_i}$$O\left(\sum_i\log r_i\right)\subseteq O\left(\sum_i\log m_i\right)\subseteq O(\log n)$$O(\log n)$

Existe outra maneira de provar a proposição 3: a saber, observe que em , precisamos apenas considerar m que são os principais poderes: m = p e . Nesse caso, os dois conjuntos incorretos que precisamos contar também possuem tamanhos que são potências de p ; em particular, se forem desiguais, diferem por um fator de pelo menos p . Assim, basta contar os tamanhos dos dois conjuntos aproximadamente . Isso pode ser feito no quasipolinômio A C 0 usando o lema de codificação de Sipser. E como já mostrado, p o w pode ser calculado em quasipolynomial $(*)$$m$$m=p^e$$p$$p$$\mathrm{AC^0}$$\mathrm{pow}$ ao quadrado repetido.$\mathrm{AC^0}$

Uma conseqüência da Proposição 3 é que, se o problema do isomorfismo abeliano não estiver em , isso pode ser um pouco difícil de provar: em particular, não se pode apenas reduzir PARIDADE ou MAIORIA ao problema, pois elas requerem tamanho exponencial circuitos de profundidade limitada, não quase-polinomial. Mesmo se tentarmos reduzir PARITY em m ≪ n bits para o problema, não há muito espaço para os parâmetros: especificamente, PARITY de super-polilogaritmicamente muitos bits não é computável por circuitos de profundidade constante de tamanho quase-polinomial e PARITY de polilogaritmicamente muitos bits já são computáveis ​​em A C 0 por divisão e conquista.$\mathrm{AC^0}$$m\ll n$$\mathrm{AC^0}$

Referências:

$\mathrm{AC^0}$

[2] David Mix Barrington, Peter Kadau, Klaus-Jörn Lange, Pierre McKenzie: Sobre a complexidade de alguns problemas nas entradas de grupos como tabelas de multiplicação , Journal of Computer and System Sciences 63 (2001), n. 2, pp. 186–200, doi: 10.1006 / jcss.2001.1764 .