¿Podemos contar en profundidad

19

¿Podemos calcular una puerta de umbral de bits por tamaño de polinomio (entrada de ventilador sin límites) de profundidad lg nn ? Alternativamente, ¿podemos contar el número de 1s en los bits de entrada usando estos circuitos?lgnlglgn

Es ?TC0AltTime(O(lgnlglgn),O(lgn))


Tenga en cuenta que . Entonces, la pregunta es esencialmente si podemos ahorrar un factor lg lg n en la profundidad de los circuitos cuando se calculan las puertas de umbral.TC0NC1=ALogTime=AltTime(O(lgn),O(lgn))lglgn


Editar:

Como Kristoffer escribió en su respuesta, podemos ahorrar un factor . ¿Pero podemos ahorrar un poco más? ¿Podemos reemplazar O ( lg nlglgncono(lgnO(lgnlglgn)?o(lgnlglgn)

Me parece que el truco de fuerza bruta en capas no funciona para guardar incluso (más generalmente cualquier función en lg lg n + ω ( 1 ) ).2lglgnlglgn+ω(1)

Kaveh
fuente
3
Modifiqué mi respuesta para incluir también la última edición.
Kristoffer Arnsfelt Hansen

Respuestas:

22

CO(logn)CO(logn/loglogn)loglogn2loglogn=lognpuertas de la última capa en el bloque de abajo. De este modo, podemos reemplazar cada puerta en la última capa por un DNF de tamaño polinómico con entradas que son las puertas en la última capa del bloque a continuación. Hacer esto para todas las puertas en las últimas capas para todos los bloques y conectarlas debería producir el circuito deseado.

logn/loglogn

Kristoffer Arnsfelt Hansen
fuente
1
Gracias Kristoffer Agregué una pregunta un poco más fuerte.
Kaveh
2
lgn/lglgnNC1
2
Así es (hasta factores constantes en la profundidad).
Kristoffer Arnsfelt Hansen