Por que os portões mod_m são interessantes?

Ryan Williams acabou de postar seu limite inferior no ACC , a classe de problemas que têm circuitos de profundidade constantes com ventiladores e portas AND ilimitados AND, OR, NOT e MOD_m para todos os m possíveis.

O que há de tão especial nos portões MOD_m?

• Eles permitem simular aritmética sobre qualquer anel Z_m.
• Antes do resultado de Ryan, jogar os portões MOD_m na mistura deu a primeira classe para a qual os limites inferiores conhecidos não funcionavam.

Existe alguma outra razão natural para estudar os portões MOD_m?

é uma classe de complexidade natural.$ACC^0$

1) Barrington mostrou que a computação sobre o não-solúvel monoides captura , enquanto ao longo monoides solúveis captura A C C 0 .$NC^1$$ACC^0$

2) Recentemente, Hansen e Koucky provaram um belo resultado que os programas de ramificação planar de largura constante de tamanho poli são exatamente . Sem a condição de planaridade, é claro que obtemos o resultado de Barrington caracterizando N C 1 .$ACC^0$$NC^1$

Portanto, a diferença entre e N C 1 é teórica de grupo, por um lado, e topológica, por outro.$ACC^0$$NC^1$

Adicionado: Dana, um exemplo simples de um grupo solucionável é , o grupo simétrico sobre os elementos. Sem entrar em detalhes, qualquer grupo solucionável possui uma série cujos quocientes são cíclicos. Essa estrutura cíclica é refletida como portas modestas durante a construção de um circuito para resolver problemas de palavras no grupo.$S_4$

Na planaridade, alguém gostaria de acreditar que a planaridade pode impor restrições / gargalos no fluxo de informações. Isso nem sempre é verdade: por exemplo, sabe-se que variações do 3SAT planar são NP-completas. No entanto, em classes menores, essas restrições são mais "prováveis" de manter.

Na mesma linha, Wigderson mostrou NL / poli = UL / poli usando o lema de isolamento. Não sabemos como derandomizar o lema de isolamento sobre DAGs arbitrários para obter NL = UL, mas sabemos como fazê-lo para DAGs planares.

$\bmod m$$m$$\bmod p$

$\bmod p$$\mathbb{F}_p$$n$

$\bmod m$$m$$2$

$AC^0[\bmod 6]$

Apenas para elaborar seus dois pontos:

Se estamos no negócio de entender a computação, a contagem modular é uma das fronteiras do nosso entendimento. A contagem modular é um dos fenômenos mais simples e naturais da computação, mas parecemos entender muito pouco sobre isso. Não podemos descartar a possibilidade de que os circuitos de profundidade de tamanho polinomial 3 com apenas portas Mod6 possam calcular todas as funções no NP. É conjecturado, no entanto, que tais circuitos só podem calcular funções com grande tamanho de suporte e, portanto, não podem calcular uma função muito simples como AND. No lado superior, a situação é semelhante, não temos resultados não triviais.

Essas perguntas também são muito interessantes de uma perspectiva puramente matemática, pois estão intimamente ligadas a questões muito naturais sobre polinômios e matrizes sobre Z_m. Para dar um exemplo, não temos bons limites inferiores para a classificação de uma matriz codiagonal nxn sobre Z_6. Uma matriz codiagonal tem 0s na diagonal e não-zero fora da diagonal.