¿Se puede realizar la adición en menos de la profundidad 5?

21

Usando el algoritmo carry look ahead podemos calcular la suma usando una familia de circuitos tamaño de polinomio de profundidad 5 (o 4?) . ¿Es posible reducir la profundidad? ¿Podemos calcular la suma de dos números binarios usando una familia de circuitos de tamaño polinómico con una profundidad menor que la obtenida por el algoritmo de anticipación de acarreo?AC0

¿Hay algún límite inferior súper polinómico para el tamaño de las familias de circuitos que calculan la suma donde d es 2 o 3?ACd0d

Por profundidad quiero decir profundidad de alternancia.

Anónimo
fuente
¿Puedes decirnos tu nombre? ¿Quien eres? ¡Durante el último mes más o menos, la gente ha creado un nuevo nombre de usuario aquí, haciendo una pregunta y luego eliminando ese nombre de usuario!
Tayfun paga el
14
@Geekster, generalmente no se requiere que las personas creen una cuenta o usen sus nombres reales (sin embargo, se recomienda hacerlo por varias razones). Si tiene alguna inquietud general acerca de algo, utilice Meta teórico de informática para plantearlo.
Kaveh
44
Esto podría ser forzado al verificar que ningún circuito de profundidad AC 0 pueda calcular la suma de ( m + 1 ) bits de dos entradas de m bits para algunos m fijos ; solo hay finitamente muchas funciones booleanas de los bits de entrada que pueden aparecer en cada profundidad. 40(m+1)mm
mjqxxxx
55
@mjqxxxx: ¿Cómo se aplica la restricción de tamaño polinómico en los circuitos AC0 cuando se fuerza a fuerza bruta para un m fijo? @ OP: ¿El mejor circuito actual es la profundidad 4 o la profundidad 5?
Robin Kothari
14
@mjqxxxx: cada función booleana es computable por los circuitos de profundidad . Ahora, suponga que encuentra para su m fijo un circuito de tamaño s . ¿Cómo juzga si hay circuitos de tamaño c n para cada n , donde c = s / m , o si solo hay circuitos de tamaño 2 ϵ n , donde ϵ = ( log s ) / m ? Simplemente no hay forma de inferir información asintótica a partir de un ejemplo finito. 2mscnnc=s/m2ϵnϵ=(logs)/m
Emil Jeřábek apoya a Monica

Respuestas:

13

Según el Teorema 3.1 en Alexis Maciel y Denis Therien Threshold Circuits of Small Majority-Depth, existe un circuito de profundidad 3 para calcular la suma de dos números.

La precisa cota es donde Δ 2 = sigma 2¸ 2 son problemas que tienen profundidad-2 A C 0 circuitos con tanto , puertas en la parte superior y N C 0 1 circuitos son N C 0 circuitos de profundidad uno (ver el documento para una explicación detallada de la notación).Δ2NC10Δ2=Σ2Π2AC0,NC10NC0

Las principales ideas de prueba son:

  • Primero, exprese el circuito Carry-lookahead como NC0Δ2NC0
  • A continuación, invoque las propiedades de cierre de para escribir esto como Δ 2N C 0Δ2Δ2NC0
  • Finalmente, use el hecho (también demostrado en el artículo) de que NC0Δ1NC10
SamiD
fuente
9

Los circuitos de profundidad 2 requieren un tamaño exponencial para calcular la suma, ya que un circuito de profundidad 2 debe ser DNF o CNF y es fácil verificar que exponencialmente hay muchos minterms y maxterms.

Advertencia : la parte de abajo tiene errores . Ver los comentarios debajo de la respuesta.

De la forma en que lo cuento, la suma se puede hacer en profundidad 3. Suponga que y b i son los bits i de los dos números, donde 0 es el índice del LSB yn del MSB. aibii0n

Calculemos el ésimo bit de la suma, S i de la manera estándar con lleva la mirada hacia el futuro:isi

si=aibici

donde es XOR y c i es el carry calculado como:ci

ci=jj<i(gjpj)

y significa que la ubicación j "generó" el carry:gjj

gj=(ajbj)

y significa que el carry se propaga de j a i :pjji

pj=kj<k<i(ajbj)

pjcisi

Noam
fuente
44
si(ci¬(aibi))(¬ci(aibi))ci
1
1
ddd(x1x2Qxdϕ(x1,,xd))(x1x2Qxdψ(x1,,xd))dd+1
1
(x1x2Qxdϕ(x1,,xd))(x1x2Q¯xdϕ(x1,,xd))
55
fn(x1,,xn)ACd0dx0fnACd0Cn(x0,,xn)Cnx0=1ACd0¬fnACd0fn