La forma más eficiente de convertir un circuito

EDITAR (22 de agosto de 2011):

Estoy simplificando aún más la pregunta y generando una recompensa por la pregunta. Quizás esta pregunta más simple tenga una respuesta fácil. También voy a tachar todas las partes de la pregunta original que ya no son relevantes. (¡Gracias a Stasys Jukna y Ryan O'Donnell por responder parcialmente la pregunta original!)

Antecedentes:

Dado un circuito AC ⁰ con profundidad k y tamaño S, existe otro circuito AC ⁰ que calcula la misma función con profundidad k y tamaño modo que el nuevo circuito tiene fanout = 1 para todas las puertas. En otras palabras, el circuito se ve como un árbol (excepto en las entradas, ya que las entradas pueden desplegarse en más de una puerta). Una forma de hacerlo es duplicando todas las puertas que tienen fanout> 1 hasta que todas las puertas tengan fanout = 1.$O(S^k)$

¿Pero es esta la forma más eficiente de convertir AC? ⁰ circuitos de CA a ⁰ circuitos con despliegue en abanico 1? Leí lo siguiente en la Lección 14 de las notas del curso de Ryan O'Donnell :

¿Significa esto que hay una manera de tomar cualquier circuito k AC ^{0 de} profundidad de tamaño S y convertirlo en un circuito AC ⁰ con fanout 1, profundidad k y tamaño ? Si es así, ¿cómo se hace esto y es este el método más conocido? $(2kS)^2$

Pregunta original

Dado un circuito AC ⁰ con profundidad k y tamaño S, ¿cuál es el método más conocido (en términos de minimizar el tamaño del circuito del circuito resultante) de convertir esto en un circuito AC ⁰ de profundidad k y puerta de salida 1? ¿Hay algún límite inferior conocido para esto?

Pregunta más nueva y simple:

Esta pregunta es una relajación de la original donde no insisto en que el circuito resultante sea de profundidad constante. Como se explicó anteriormente, hay una manera de convertir un circuito AC ⁰ con profundidad k, tamaño S en un circuito con tamaño modo que el nuevo circuito tenga un fanout = 1 para todas las puertas. ¿Hay una mejor construcción?$O(S^k)$

Dado un circuito AC ⁰ con profundidad k y tamaño S, ¿cuál es el método más conocido (en términos de minimizar el tamaño del circuito del circuito resultante) de convertir esto a un circuito de cualquier profundidad con puerta de salida 1?

Intentaré resumir mis comentarios anteriores.

Primero ignoremos el hecho de que su circuito original tiene una profundidad (constante) ; acaba de asumir que tiene el tamaño S . Sea A el número más pequeño, de modo que cada tamaño de circuito de ventilador sin límites S pueda transformarse en una fórmula de ventilador sin límites F de tamaño O ( S A ) . Afirmo que lo mejor que podemos hacer hasta ahora es lograr A = O ( S / log 2 S ) . Digamos, incluso no se sabe si hay algún circuito (fanin-2) de tamaño S = O ( n $k$$S$$A$$S$$F$$O(S^A)$$A=O(S/\log^2 S)$$S=O(n)$se puede simular con una fórmula de tamaño menor que .$\exp(n/\log n)$

Para mostrar el reclamo, transformamos la fórmula en una fórmula fanin-2 F ' de tamaño M = O ( S 2 A ) . Es bien sabido que la profundidad D de cada fórmula F ' puede hacerse logarítmica en su tamaño, es decir D = O ( log M ) = O ( A log S ) . [Esto fue demostrado por primera vez por Khrapchenko 1968, y luego la constante bajo big-O se mejoró a D ≤ 1.73 log 2$F$$F′$$M=O(S^{2A})$$D$$F′$$D=O(\log M)=O(A\log S)$$D\leq 1.73\log_2M$por varios autores.] Por otro lado, el resultado más conocido para los circuitos fanin-2 [Paterson y Valiant, TCS 2 (3), 397-400] dice que . Por lo tanto, tener una simulación con A mucho más pequeña que S / log 2 S mejoraría la simulación de tamaño-profundidad más conocida para circuitos.$Depth=O(Size/\log Size)$$A$$S/\log^2 S$

Sin embargo, esto es solo una "palabra de precaución": no responde a su pregunta porque supone que su circuito original tiene una profundidad constante , lo que implica que en este caso solo podemos tomar A = k (o A = k - 1 si tenemos una sola puerta de salida). ¡El poder de la simulación Paterson-Valiant es que se aplica a circuitos arbitrarios, incluso muy desequilibrados, cuya profundidad es casi del tamaño completo! Pero en su configuración de profundidad acotada, incluso el caso k = 3 no está claro: ¿puede cada circuito de profundidad 3 de tamaño S transformarse en una fórmula de profundidad 3 de tamaño mucho más pequeño que S $k$$A=k$$A=k−1$$k=3$$S$$S^2$? Supongo que la respuesta debería ser "no" (podría ser un ejercicio interesante para los estudiantes). Una fórmula de profundidad 3 es solo un gran OR de CNF. La pregunta es encontrar un OR de CNF que compartan muchas cláusulas en común, pero que por lo demás sean "muy diferentes" para forzar una fórmula grande de profundidad 3.

El problema es que queremos obtener una fórmula (un circuito fanout-1). Como se señaló anteriormente, permitir puertas de fanout-2 simplifica la simulación: Hoover, Klawe y Pippenger [JACM 31 (1), 1980] muestran que cualquier circuito fanin-2 de tamaño y profundidad D tiene un fanin-2 y fanout equivalentes -2 circuito de tamaño 3 S - 2 n y la profundidad 2 D . Por lo tanto, si fanin no tiene límites, el circuito resultante tendrá un tamaño O ( S 2 ) y una profundidad O ( D log S ) .$S$$D$$3S−2n$$2D$$O(S^2)$$O(D\log S)$

Hay otro resultado relacionado de alguna manera con su pregunta. Lozhkin (1981) demostró que si una función booleana puede calcularse mediante una fórmula A C 0 de profundidad k y tamaño S , entonces f puede calcularse mediante una fórmula fanin-2 de profundidad D ≤ k - 1 + ⌈ log 2 S ⌉ (Esto se desprende del Teorema 6.2 en mi libro). Tenga en cuenta que un límite superior trivial solo sería D ≤ k log S (si simulamos cada puerta por un árbol de profundidad log S ).$f$$AC^0$ $k$$S$$f$$D\leq k-1+\lceil\log_2S\rceil$$D\leq k\log S$$\log S$