¿Límites inferiores para fórmulas de profundidad constante?

Sabemos mucho sobre las limitaciones de los circuitos de profundidad constante (tamaño polinómico). Dado que las fórmulas (de tamaño polinómico) de profundidad constante son un modelo de cálculo aún más restringido, todos los problemas que se sabe que no están en AC ⁰ tampoco son computables por una fórmula de profundidad constante. Sin embargo, dado que es un modelo más fácil, supongo que hay más problemas que se sabe que no son computables en este modelo. ¿Se ha estudiado esto? (Supongo que lo ha sido, pero probablemente no estoy usando los términos de búsqueda correctos).

Específicamente, estoy interesado en la siguiente pregunta: ¿Hay alguna función f, que pueda ser calculada por un circuito AC ⁰ de tamaño S, pero necesita una fórmula de tamaño de profundidad constante al menos cuadrática en S o superpolinomial en S? ¿Cuál es el resultado más conocido de este tipo?

En caso de que no esté claro a qué me refiero con fórmula de profundidad constante, me refiero a una fórmula que si escribe como un árbol (con nodos internos como puertas AND / OR / NOT, y las hojas son entradas), entonces este árbol tiene constante altura. De manera equivalente, una fórmula de profundidad constante es un circuito de profundidad constante en el que todas las puertas sin entrada tienen un fanout 1.

Es fácil convertir un circuito de profundidad constante en una fórmula de profundidad constante de la misma profundidad con un aumento de tamaño polinómico, haciendo copias de las compuertas utilizadas más de una vez. Si la profundidad del circuito es y su tamaño es O ( p ( n ) ) , la fórmula tendrá profundidad d y tamaño O ( ( p ( n ) ) d ) . Por lo tanto, la respuesta es no.$d$$O(p(n))$$d$$O((p(n))^d)$

Esta pregunta ha sido completamente resuelta (hasta factores constantes) por un resultado reciente de Benjamin Rossman ( http://eccc.hpi-web.de/report/2013/169/ ).

Como Kaveh señala anteriormente, un circuito de profundidad , tamaño S , se puede convertir en una fórmula de profundidad d , tamaño S d .$d$$S$$d$$S^d$

Rossman muestra que esto es esencialmente apretado. Para cualquier profundidad , exhibe una función que puede ser calculada por un circuito de profundidad constante de profundidad d y tamaño S = O ( n 3 ) , pero cualquier fórmula de profundidad constante (o incluso un $d$$d$$S = O(n^3)$ -depth formula) necesita el tamañoS Ω ( d ) para calcularlo.$\sqrt{\log n}$$S^{\Omega(d)}$

(Olvidé decir esto antes: gracias a Benjamin Rossman por informarme sobre este resultado).