Lista de problemas numéricos ou algébricos em várias classes de complexidade

Estou procurando uma lista sobre a complexidade conhecida ou desconhecida de vários problemas teóricos / algébricos de números. Por exemplo,

• GCD em está aberto,$NC^1$
• factoring em é aberto,$P$
• a cohomologia do feixe de computação é -hard$\#P$ ,
• Arora e Barak afirmam que uma variante de fatoração é completa (embora isso não esteja claro com base na discussão em Uma variante de fatoração NP-completa ) .$NP$
• O trabalho inovador de Barbulescu et al. Sobre logaritmos discretos .

Adleman uma vez publicou uma lista focada em e mas parece desatualizada. Mumford tem um artigo sobre o que é computável em geometria algébrica, sem levar em conta a complexidade.N $P$$NP$

Alguém conhece uma lista de (principais) descobertas desde que essas listas foram publicadas?

Quais são alguns problemas de um número teórico / algébrico cujas classes de complexidade já são conhecidas (desde que as listas acima foram publicadas), desconhecidas, mas conjecturadas, ou desconhecidas e não conjecturadas?

Algumas vias de problemas podem ser problemas de interpolação (univariada ou multivariada, em vários campos), teorema do restante chinês, complexidade da contagem de pontos nas curvas, etc.

Geometria algébrica

• Atualmente, o lema de normalização de Noether (NNL) para variedades explícitas é conhecido apenas em (como o NNL geral), mas é conjecturado como estando em (e está em assumindo que o PIT pode ser des caixa aleatoriamente). Atualização 18/4/18: Foi recentemente demonstrado que, para a variedade ela está em sobre os racionais ( Forbes e Shpilka) e depois sobre campos arbitrários ( Guo, Saxena, E Sinhababu ).P P ¯ V P P S P A C $\mathsf{EXPSPACE}$$\mathsf{P}$$\mathsf{P}$$\overline{\mathsf{VP}}$$\mathsf{PSPACE}$

• Testando se um determinado conjunto de polinômios tem uma dependência algébrica. Foi demonstrado recentemente que esse problema está em de Guo, Saxena e Sinhababu (aprimorando o limite superior anterior de devido para Mittmann, Saxena e Scheblechner , também no arXiv ).N P # $\mathsf{AM} \cap \mathsf{coAM}$$\mathsf{NP}^{\mathsf{\# P}}$

• Existem vários novos algoritmos ( arXiv ) para calcular invariantes topológicos de variedades complexas (com várias restrições, como suavidade, etc.). Acredito que para a maioria deles o limite superior ideal ainda está aberto.

• Nullstellensatz (HN) de Hilbert: dados polinômios inteiros, decidem se eles têm uma solução complexa comum, está em assumindo GRH ( Koiran ). Não se sabe se está em .N $\mathsf{AM}$$\mathsf{NP}$

• Algoritmos para resolução de singularidades de variedades algébricas na característica zero. O limite superior do melhor horário atual , devido a Bierstone, Grigoriev, Milman e Włodarczyk é que é a dimensão da variedade e é o Hierarquia de Grzegorczyk de funções recursivas primitivas . Não há limites inferiores particularmente bons (existem?) Para esse problema, mas para problemas aparentemente mais simples, os limites inferiores são conhecidos, a saber: Existem ideais em variáveis ​​geradas em grau no máximo que requerem d E n nn E n + $\mathcal{E}^{d+3}$$d$$\mathcal{E}^{\bullet}$$n$$n$$\mathcal{E}^{n+1}$tais geradores. Portanto, o atual limite superior para a resolução de singularidades pode não estar longe da verdade, mas pouco se sabe realmente.

Problemas de isomorfismo

• Muitos problemas em grupos de permutação - como interseção de coset, isomorfismo de grupo de permutação etc. - estão em , mas não se sabe se eles estão em e suspeita-se que eles não estejam em . O isomorfismo do gráfico se reduz à maioria desses problemas; portanto, um melhor limite superior implica um melhor limite superior no IG.N P ∩ C o N P $\mathsf{NP} \cap \mathsf{coAM}$$\mathsf{NP} \cap \mathsf{coNP}$$\mathsf{P}$

• Em particular, para o isomorfismo do grupo de permutação, o melhor limite superior atual é, e está aberto se isso puder ser feito em tempo (dependendo apenas do grau do grupo de permutação e não em sua ordem), sem falar no tempo quase poli, como a intersecção GI e coset .2 O ( n $2^{O(n)}|G|$$2^{O(n)}$

• O isomorfismo do grupo em que os grupos são dados por tabelas de multiplicação é conhecido por estar em , mas suspeita-se que esteja em . Conhecido por ser em para várias aulas de grupos (atualização 4/18/18: e um casal ( arXiv ) mais ( arXiv )), mas não em geral.P $\mathsf{TIME}(n^{O(\log n)})$$\mathsf{P}$$\mathsf{P}$

De outros

• Atualização 18/4/18: A classificação do tensor em qualquer campo é concluída ( Schaefer & Stefankovic ). A classificação do tensor está acima de em ? É conhecido por ser -hard ( Håstad ) e, sobre campos finitos, está em . ∃ F Q N P N P N $\mathbb{F}$$\exists \mathbb{F}$$\mathbb{Q}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$

• De maneira mais geral, muitos problemas nos tensores acima de são -hard, mas não se sabe que estejam em ( Hillar e Lim , também no arXiv ).N P N $\mathbb{Q}$$\mathsf{NP}$$\mathsf{NP}$

Parece (um pouco triste) que a pesquisa Adleman-McCurley, apesar de ter 21 anos, esteja bastante atualizada em termos de problemas teóricos dos números, com exceção do fato de que agora sabemos que é em ...$\mathsf{PRIMES}$$\mathsf{P}$

Adicionando um pouco mais com ênfase na teoria de Galois e na teoria computacional de Galois (veja a pergunta relacionada no cs.SE ):

$\mathbb{Z}$$\mathbb{P}$

$NP$

reproduzido da pergunta vinculada no MO