Lista de problemas teóricos o algebraicos de números en varias clases de complejidad

12

Estoy buscando una lista sobre la complejidad conocida o desconocida de varios problemas teóricos / algebraicos de números. Por ejemplo,

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.PNP

¿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.

T ....
fuente
¿Realmente desea solo problemas cuya complejidad no solo no se conoce, sino que ni siquiera se especula que esté en algún lugar? Eso parece bastante restrictivo, por ejemplo, la factorización de enteros no satisfaría esa pregunta, ya que se especula que está en un punto intermedio entre P y ... Pero creo que (y espero) te refieres a una pregunta un poco más permisiva. Sería interesante ver esa lista. UPcoUP
Joshua Grochow
@JoshuaGrochow se amplió.
T ....
¿Se sabe que GCD está en el espacio de registro?
44
No, es un problema abierto si está en cualquier lugar de la jerarquía de CN.
Emil Jeřábek

Respuestas:

18

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 ).EXPSPACEPPVP¯PSPACE

  • AMcoAMNP#P

  • 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.

  • AMNP

  • Ed+3dEnnEn+1tales generadores Por lo tanto, el límite superior actual para la resolución de singularidades puede no estar muy lejos de la verdad, pero realmente se sabe poco.

Problemas de isomorfismo

  • NPcoAMNPcoNPP

  • 2O(n)|G|2O(n)

  • TIME(nO(logn))PP

Otro

  • FFQNPNPNP

  • QNPNP

PRIMESP

Joshua Grochow
fuente
Me sorprende que HN esté en NP es desconocido. Todo lo que tienes que hacer es verificar la solución para cada polinomio ¿verdad?
T ....
¿Cuál es la brecha en la resolución de singularidades?
T ....
44
@Turbo: para HN, los polinomios son polinomios enteros, pero las soluciones pueden ser números complejos que ni siquiera necesitan ser expresados ​​por un número finito de bits, y mucho menos un número polinómico de bits. Además, incluso para recibir AM, creo que necesitas GRH.
Joshua Grochow
2
(Primero confirmo que la prueba de que HN está en AM se basa en GRH). @Turbo: La entrada es un conjunto de polinomios enteros, así definidos con un número finito de bits. Un certificado obvio para HN sería una solución para el sistema. Pero lo que Joshua dice es que la descripción de tal solución no es necesariamente representable con un número finito de bits. ¡Por lo tanto, estamos lejos de tener un certificado de tamaño polinómico !
Bruno
3
@Nikhil: porque PIT no da un límite superior en NNL. Los conjuntos de bateo de caja negra son los que dan el límite. El problema con la enumeración de todos los conjuntos de golpes posibles para NNL (el algoritmo PSPACE para PIT) es que para cada uno, se debe verificar una determinada propiedad, y esa verificación solo se sabe que está en EXPSPACE. Si OTOH puede construir directamente un conjunto de golpes garantizado, básicamente no tiene que verificarlo. Verás cuando leas el periódico.
Joshua Grochow