¿Hay alguna referencia que proporcione detalles sobre los límites inferiores del circuito para problemas difíciles específicos que surgen en la criptografía, como la factorización de enteros, el problema de logaritmo discreto primario / compuesto y su variante sobre el grupo de puntos de curvas elípticas (y sus variedades abelianas de dimensiones superiores) y el general problema de subgrupo oculto?
Específicamente, ¿alguno de estos problemas tiene más que un límite inferior de complejidad lineal?
Respuestas:
@Suresh: siguiendo tu consejo, aquí está mi "respuesta". El estado de los límites inferiores del circuito es bastante deprimente. Aquí están los "registros actuales":
Entonces, su pregunta "¿Específicamente alguno de estos problemas tiene más que un límite inferior de complejidad lineal?" permanece ampliamente abierto (en el caso de los circuitos). Mi llamado a todos los investigadores jóvenes: ¡adelante, estas "barreras" no son irrompibles! Pero trate de pensar de una manera "no natural", en el sentido de Razborov y Rudich.
fuente