Las pruebas naturales son una barrera para probar los límites inferiores de la complejidad del circuito de las funciones booleanas. Ellos no implican directamente cualquier barrera en probar límites inferiores en el la complejidad del circuito. ¿Hay algún progreso hacia la identificación de tales barreras? ¿Existen otras barreras en el entorno monótono?
cc.complexity-theory
circuit-complexity
barriers
natural-proofs
Shiva Kintali
fuente
fuente
85, Alon+Boppana
87).Respuestas:
El reciente artículo de Benjamin Rossman resume el estado del arte de la complejidad del circuito monótono de k-CLIQUE. En resumen, Razborov demostró un límite inferior en 1985, luego mejorado por Alon y Boppana en 1987: , frente a la fuerza bruta O límite superior ( n k ) .ω ( nk/ (logn )k) O ( nk)
Rossman muestra un límite inferior de para la complejidad del caso promedio en el modelo de gráficos aleatorios Erdős-Rényi; Amano demostró previamente que esto era esencialmente también el límite superior. El lema cuasi-girasol que forma una parte clave del papel es bastante limpio.ω ( nk / 4)
Por lo tanto, la barrera de las pruebas naturales no parece aplicarse a la complejidad del circuito monótono.
Norbert Blum ha discutido por qué los límites inferiores para los circuitos monótonos son esencialmente diferentes de los circuitos con negaciones. La observación clave de Éva Tardos es que una pequeña modificación de la función theta de Lovász tiene una complejidad de circuito monótono exponencial.
fuente
Al punto se le da una función booleana general f, hay una función booleana monótona g, de modo que cualquier límite inferior super lineal en g implica uno en f. O más fuerte, la complejidad general de f es igual a la complejidad monótona de g hasta O (n).
Todavía no estoy seguro de cómo se relaciona esto con las barreras.
fuente