Circuitos aritméticos monótonos

El estado de nuestro conocimiento sobre los circuitos aritméticos generales parece ser similar al estado de nuestro conocimiento sobre los circuitos booleanos, es decir, no tenemos buenos límites inferiores. Por otro lado, tenemos límites inferiores de tamaño exponencial para circuitos booleanos monótonos .

¿Qué sabemos sobre los circuitos aritméticos monótonos ? ¿Tenemos similares límites inferiores buenos para ellos? Si no, ¿cuál es la diferencia esencial que no nos permite obtener límites inferiores similares para circuitos aritméticos monótonos?

La pregunta está inspirada en los comentarios sobre esta pregunta .

Los límites inferiores para los circuitos aritméticos monótonos son más fáciles porque prohíben las cancelaciones. Por otro lado, podemos probar los límites inferiores exponenciales para los circuitos de computación funciones booleanas incluso si alguna monótonas valorados en tiempo real, funciones se permiten las puertas (véase, por ejemplo Sección 9.6 en el. Libro ).$g:R\times R\to R$

Aunque los circuitos aritméticos monótonos son más débiles que los circuitos booleanos monótonos (en este último tenemos cancelaciones y ), estos circuitos son interesantes debido a su relación con la programación dinámica ( DP) algoritmos. La mayoría de estos algoritmos pueden ser simulados por circuitos sobre semirremolques oa ∨ ( a ∧ b ) = a ( + , min ) ( + , max $a\land a=a$$a\lor (a\land b)=a$$(+,\min)$$(+,\max)$. Las puertas corresponden a subproblemas utilizados por el algoritmo. Lo que Jerrum y Snir (en el artículo de V Vinay) prueban realmente es que cualquier algoritmo DP para la coincidencia perfecta de peso mínimo (así como para el problema TSP) debe producir exponencialmente muchos subproblemas. Pero el problema de Perfect Mathching no es "DP flawor" (no satisface el Principio de Optimidad de Bellman ). La programación lineal (no DP) es mucho más adecuada para este problema.

Entonces, ¿qué pasa con los problemas de optimización que pueden resolverse con algoritmos DP razonablemente pequeños? ¿Podemos probar límites más bajos también para ellos? Muy interesante a este respecto es un viejo resultado de Kerr (Teorema 6.1 en su doctorado ). Implica que el algoritmo clásico Floyd-Warshall DP para el problema de los caminos más cortos de todos los pares (APSP) es óptimo : son necesarios subproblemas . Aún más interesante es que el argumento de Kerr es muy simple (mucho más simple que el que usaron Jerrum y Snir): solo usa el axioma de distributividad , y la posibilidad de "matar" puertas mínimas estableciendo uno de sus argumentos en forma, él demuestra que$\Omega(n^3)$$a+\min(b,c)=\min(a,b)+\min(a,c)$$0$$n^3$las compuertas plus son necesarias para multiplicar dos matrices sobre el semiring . En la secta. 5.9 del libro de Aho, Hopcroft y Ullman se muestra que este problema es equivalente al problema de APSP.$n\times n$$(+,\min)$

La siguiente pregunta podría ser: ¿qué pasa con el problema de las rutas más cortas de fuente única (SSSP)? El algoritmo DP de Bellman-Ford para este problema (aparentemente "más simple") también utiliza puertas . ¿Es esto óptimo? Hasta el momento, no se conoce separación entre estas dos versiones del problema del camino más corto; Vea un interesante artículo de Virginia y Ryan Williams en esta línea. Entonces, un límite inferior en los circuitos para SSSP sería un gran resultado. La siguiente pregunta podría ser: ¿qué pasa con los límites inferiores para la mochila? En este borrador, los límites inferiores para la mochila se prueban en un modelo más débil de circuitos donde el uso de$O(n^3)$$\Omega(n^3)$$(+,\min)$$(+,\max)$$+$-gate está restringido; en el apéndice se reproduce la prueba de Kerr.

Sí. Conocemos buenos límites inferiores y los conocemos desde hace bastante tiempo.

Jerrum y Snir demostraron un límite inferior exponencial sobre circuitos aritméticos monótonos para el permanente en 1980. Valiant demostró que incluso una sola puerta negativa es exponencialmente más poderosa .

Para obtener más información sobre los circuitos aritméticos (monótonos), consulte la encuesta de Shpilka sobre circuitos aritméticos.

$2k$$k$

¿Cuenta esto: los límites inferiores del semi-grupo de Chazelle para problemas fundamentales de búsqueda de rango (en la configuración fuera de línea). Todos los límites inferiores son casi óptimos (hasta los términos de registro cuando los límites inferiores son polinomiales y los términos de registro cuando el límite inferior es poliligarítmico).