¿Alguien ha explorado cuál es la complejidad del circuito de los problemas de decisión clásicos como Primes o Graph-Isomorphism para un tamaño de entrada pequeño ?
Si bien la mayoría de la gente está interesada en cómo va la escala según , creo que también sería interesante ver cómo crece esto para el pequeño N. Seguro, ahora sabemos que Primes está en P, pero sería bueno vea cómo crece, y tal vez incluso cambios bruscos en la tasa de crecimiento del gráfico a medida que las entradas se hacen lo suficientemente grandes como para que un algoritmo diferente se vuelva más eficiente.
Incluso existe la posibilidad (improbable) de que alguien pueda extraer de una secuencia de circuitos un algoritmo general.
Parece que este enfoque podría responder preguntas diferentes de las que generalmente se hacen sobre . Con los avances del conocimiento de los algoritmos (solucionadores SAT, etc.) y la super potencia informática, se podrían obtener respuestas concretas para pequeño .
¿Hay referencias o listas de resultados para personas que calculan explícitamente la complejidad del circuito de problemas de decisión para pequeñas ?
Si hay personas trabajando en esto, ¿qué algoritmos usan actualmente para resolver el problema del circuito mínimo (dada una función booleana y un conjunto de compuertas, emite un circuito utilizando el número mínimo de compuertas necesario)?
Respuestas:
Sí, esta es una idea natural y la gente lo ha pensado. En resumen, el problema es que incluso los solucionadores SAT / QBF de última generación permiten encontrar solo circuitos muy pequeños (con aproximadamente 10–12 puertas), por no decir que demuestran que no hay un circuito pequeño. Algunas referencias:
fuente
En muchos modelos no uniformes (circuitos booleanos, circuitos algebraicos, árboles de decisión, programas de ramificación, etc.), calcular la complejidad exacta parece ser significativamente más difícil que calcular la complejidad asintótica. Si bien mantengo la esperanza de que su intuición sea correcta, que la comprensión de la complejidad exacta de las instancias pequeñas pueda conducir a ideas asintóticas, solo conozco algunos casos en los que esto ha sucedido:
Algoritmos y límites inferiores para la multiplicación matricial de pequeños formatos. Ha habido una buena cantidad de trabajo en 2x2 ( Strassen ), 3x3 ( Laderman ) y otros formatos pequeños para la multiplicación de matrices (ver también Johnson-McLoughlin y Hopcroft-Kerr ). Originalmente, estos a menudo se podían usar para dar mejoras asintóticas, debido a la estructura recursiva de la multiplicación de matrices. Finalmente, Coppersmith-Winograd suplantó todo esto en el reino asintótico.
Los límites inferiores de estilo GCT en la multiplicación de matrices pequeñas debido a Bürgisser e Ikenmeyer han producido límites inferiores asintóticos en la multiplicación de matrices. Creo que esto es al menos parcialmente porque la estructura teórica de la representación sugiere naturalmente cómo convertir un límite inferior único y exacto en una familia infinita.
(Ver la respuesta de Alexander Kulikov para un par más)
Aparte de estos, ha habido una cantidad pequeña pero no trivial de trabajo sobre la complejidad exacta de varios problemas, pero en su mayoría problemas más fáciles que GraphIso o Primes (excepto el último ejemplo de lo permanente). Si bien considero que este trabajo es interesante y mantengo la esperanza de que conducirá a una comprensión teórica más amplia, que yo sepa, aún no lo ha hecho.
Knuth consideró la cuestión del número exacto de comparaciones necesarias para ordenar una lista de elementos en el Capítulo 5, vol. 3 de TAOCP . Se han realizado más progresos desde entonces (ver el trabajo de Peczarski , y referencias al respecto).n
También se ha trabajado en redes de clasificación de profundidad mínima exacta ( Bundala y Závodný parecen ser las últimas).
Con una complejidad exacta, puede haber efectos teóricos numéricos debido al tamaño de la entrada. (Cuando se trata de un algoritmo de divide y vencerás, por ejemplo, es fácil imaginar cómo las entradas de tamaño pueden diferir de las entradas de tamaño impar cuando se trata de la complejidad exacta). Ver Drmota y Szpankowski para ejemplos de esto , así como un teorema maestro exacto.2k
Complejidad determinante de pequeños permanentes (límite superior por B. Grenet y límite inferior reciente en por Alper, Bogart y Velasco ) y otras funciones ( Qiao, Sun y Yu ).per3
fuente