¿Existe un límite inferior mejor que el lineal para la factorización y el registro discreto?

19

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

vs
fuente
99
Usted, por supuesto, sabe que no se conoce un límite inferior mejor que 5n para la complejidad del circuito, para <i> cualquier </i> función explícita, no solo para las que ha mencionado. Entonces, debe especificar la pregunta. Los mejores límites solo se conocen para circuitos restringidos . Quizás podría encontrar algunas respuestas parciales en la página de inicio de <a href=" web.science.mq.edu.au/~igor "rel="nofollow"> Igor Sparlinski. </a>
Stasys
8
Bueno, no estoy muy seguro de qué quieres decir con "este hecho interesante". De todos modos, el estado actual del arte en la complejidad del circuito se da en mi próximo libro thi.informatik.uni-frankfurt.de/~jukna/BFC-book . Usuario: amigo Contraseña: catchthecat
Stasys
1
@Stasys, recuerdo que un estudiante de Rusia habló sobre su límite inferior del formulario 7n + O (1) basado en la eliminación de la puerta en la Escuela de Otoño de Praga hace dos años, pero no puedo recordar más detalles.
Kaveh
12
Kaveh, este es un límite inferior (7/3) nc, no 7n. Fue probado por Arist Kojevnikov y Sasha Kulikov de Petersburgo. La ventaja de su prueba es su simplicidad, no numérica. Más tarde, dieron una prueba simple del límite inferior 3n-o (1) para circuitos generales (se permiten todas las puertas fanin-2). Aunque para funciones muy complicadas: dispersores afines. Los documentos están en línea en: logic.pdmi.ras.ru/~kulikov/papers . En realidad, Redkin (1973) mostró el límite apretado 7n-7 para la función de paridad, pero solo si se permiten las puertas NOT y AND. Si también se permite OR, entonces su límite es 4n-4 (¡también apretado!).
Stasys
55
@StasysJukna: una combinación de sus comentarios es apropiada como respuesta.
Suresh Venkat

Respuestas:

26

@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":

  • para circuitos sobre { , , ¬ } , y 7 n - 7 para circuitos sobre { , ¬ } y { , ¬ } computaciónn ( x ) = x 1x 2x n ; Redkin (1973). Estos límites son ajustados. 4 4norte-4 4{,,¬}7 7norte-7 7{,¬}{,¬}norte(X)=X1X2Xnorte
  • para circuitos sobre la base con todas las compuertas fanin-2, excepto la paridad y su negación; Iwama y Morizumi (2002). 5 5norte-o(norte)
  • para circuitos generales sobre la base con todas las puertas fanin-2; Blum (1984). Arist Kojevnikov y Sasha Kulikov de Petersburgo han encontrado una prueba más simple de un ( 7 / 3 ) n - O ( 1 ) el límite inferior. La ventaja de su prueba es su simplicidad, no numérica. Más tarde dieron una prueba simple de 3 n - o ( 1 ) límite inferior para circuitos generales (se permiten todas las puertas fanin-2). Aunque para funciones muy complicadas: dispersores afines. Los documentos están en líneaaquí. 3norte-o(norte)(7 7/ /3)norte-o(1)3norte-o(1)
  • para fórmulas sobre { , , ¬ } ; Hastad (1998). norte3-o(1){,,¬}
  • para generales fanin- 2 fórmulas, Ω ( n 2 / log 2 n ) para los programas de ramificación deterministas, y Ω ( n 3 / 2 / log n ) para los programas de ramificación no deterministas; Nechiporuk ~ (1966). Ω(norte2/ /Iniciar sesiónnorte)2Ω(norte2/ /Iniciar sesión2norte)Ω(norte3/ /2/ /Iniciar sesiónnorte)

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.

Stasys
fuente
¿Es este el papel de Hastad 1998? nada.kth.se/~johanh/monotoneconnect.pdf No creo que el enlace implique 'no'. Además, el exponente es cuadrático.
T ....
@JA: No, este es otro de sus trabajos del mismo año J. Håstad, The Shrinkage Exponent is 2, SIAM Journal on Computing, 1998, Vol 27, pp 48-64.
Stasys
(3+Ω(1))norte