Estoy buscando una lista sobre la complejidad conocida o desconocida de varios problemas teóricos / algebraicos de números. Por ejemplo,
- El MCD en está abierto,
- factoring en está abierto,
- la cohomología informática de la gavilla es -duro ,
- Arora y Barak afirman que una variante de factorización es -completa (aunque esto no está claro en base a la discusión en An NP-complete variant of factoring ),
- El avance de Barbulescu et al. Sobre logaritmos discretos .
Adleman una vez publicó una lista centrada en y N P, pero parece anticuada. Mumford tiene un artículo sobre lo que es computable en geometría algebraica sin tener en cuenta la complejidad.
¿Alguien sabe una lista de descubrimientos (principales) desde que se publicaron estas listas?
¿Cuáles son algunos problemas de un sabor teórico / algebraico numérico cuyas clases de complejidad posiblemente ya se conocen (desde que se publicaron las listas anteriores), desconocido pero conjeturado, o desconocido y no conjeturado?
Algunas vías de problemas podrían ser problemas de interpolación (univariados o multivariados, en varios campos), el teorema del resto chino, la complejidad del conteo de puntos sobre curvas, etc.
Respuestas:
Geometría algebraica
El Lema de normalización de Noether (NNL) para variedades explícitas actualmente solo se sabe que está en (como NNL general), pero se conjetura que está en P (y está en P suponiendo que PIT puede ser caja negra desrandomizado). Actualización 18/04/18: Recientemente se demostró que para la variedad ¯ V P está en P S P A C E sobre los racionales ( Forbes y Shpilka) y luego sobre campos arbitrarios ( Guo, Saxena y Sinhababu ).EXPSPACE P P VP¯¯¯¯¯¯¯ PSPACE
Existen varios ( arXiv ) nuevos algoritmos para calcular invariantes topológicos de variedades complejas (con varias restricciones como la suavidad, etc.). Creo que para la mayoría de estos, el límite superior óptimo aún está abierto.
Problemas de isomorfismo
Otro
fuente
Agregando algunos más con énfasis en la teoría de Galois y la teoría computacional de Galois (vea la pregunta relacionada en cs.SE ):
reproducido de la pregunta vinculada en MO
fuente