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

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? $AC^0$

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

Por profundidad quiero decir profundidad de alternancia.

cc.complexity-theory circuit-complexity lower-bounds upper-bounds 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

@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

Esto podría ser forzado al verificar que ningún circuito de profundidad

pueda calcular la suma de

bits de dos entradas de

bits para algunos

fijos ; solo hay finitamente muchas funciones booleanas de los bits de entrada que pueden aparecer en cada profundidad.

4

$4$

^{0}

$^{0}$

(m + 1)

$(m+1)$

m

$m$

m

$m$

mjqxxxx

@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

@mjqxxxx: cada función booleana es computable por los circuitos de profundidad

. Ahora, suponga que encuentra para su

fijo un circuito de tamaño

. ¿Cómo juzga si hay circuitos de tamaño

para cada

, donde

, o si solo hay circuitos de tamaño

, donde

? Simplemente no hay forma de inferir información asintótica a partir de un ejemplo finito.

2

$2$

m

$m$

s

$s$

c n

$cn$

n

$n$

c = s / m

$c=s/m$

2^{ϵ n}

$2^{\epsilon n}$

ϵ = (\log s) / m

$\epsilon=(\log s)/m$

Emil Jeřábek apoya a Monica

Respuestas:

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 son problemas que tienen profundidad-2 circuitos con tanto puertas en la parte superior y circuitos son circuitos de profundidad uno (ver el documento para una explicación detallada de la notación). $\Delta_2 \cdot \mathsf{NC}^0_1$ $\Delta_2 = \Sigma_2 \cap \Pi_2$ $\mathsf{AC}^0$ $\vee,\wedge$ $\mathsf{NC}^0_1$ $\mathsf{NC}^0$

Las principales ideas de prueba son:

Primero, exprese el circuito Carry-lookahead como $\mathsf{NC}^0\cdot\Delta_2\cdot\mathsf{NC}^0$
A continuación, invoque las propiedades de cierre de para escribir esto como $\Delta_2$ $\Delta_2\cdot\mathsf{NC}^0$
Finalmente, use el hecho (también demostrado en el artículo) de que $\mathsf{NC}^0 \subset \Delta_1\cdot\mathsf{NC}^0_1$

SamiD
fuente

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 son los bits de los dos números, donde es el índice del LSB del MSB. $a_i$ $b_i$ $i$ $0$ $n$

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

s_{i} = a_{i} \oplus b_{i} \oplus c_{i}

$s_i = a_i \oplus b_i \oplus c_i$

donde es XOR y es el carry calculado como: $\oplus$ $c_i$

c_{i} = \underset{j ∣ j < i}{⋁} (g_{j} \land p_{j})

$c_i = \bigvee_{j\mid j < i} (g_j \wedge p_j)$

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

g_{j} = (a_{j} \land b_{j})

$g_j = (a_j \wedge b_j)$

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

p_{j} = \underset{k ∣ j < k < i}{⋀} (a_{j} \lor b_{j})

$p_j = \bigwedge_{k\mid j < k < i} (a_j \vee b_j)$

$p_j$ $c_i$ $s_i$

Noam
fuente

s_{i}

$s_i$

(c_{i} \land \neg (a_{i} \oplus b_{i})) \lor (\neg c_{i} \land (a_{i} \oplus b_{i}))

$(c_i\land\neg(a_i\oplus b_i))\lor(\neg c_i\land(a_i\oplus b_i))$

⋁

$\bigvee$

⋀

$\bigwedge$

c_{i}

$c_i$

⋀

$\bigwedge$

d

$d$

d

$d$

d

$d$

(\forall x_{1} \exists x_{2} \dots Q x_{d} ϕ (x_{1}, \dots, x_{d})) \lor (\forall x_{1} \exists x_{2} \dots Q x_{d} ψ (x_{1}, \dots, x_{d}))

$(\forall x_1\exists x_2\dots Qx_d\phi(x_1,\dots,x_d))\lor(\forall x_1\exists x_2\dots Qx_d\psi(x_1,\dots,x_d))$

d

$d$

d + 1

$d+1$

(\forall x_{1} \exists x_{2} \dots Q x_{d} ϕ (x_{1}, \dots, x_{d})) \lor (\exists x_{1} \forall x_{2} \dots \bar{Q} x_{d} ϕ (x_{1}, \dots, x_{d}))

$(\forall x_1\exists x_2\dots Qx_d\phi(x_1,\dots,x_d))\lor(\exists x_1\forall x_2\dots \overline Qx_d\phi(x_1,\dots,x_d))$

f_{n} (x_{1}, \dots, x_{n})

$f_n(x_1,\dots,x_n)$

A C_{d}^{0}

$AC^0_d$

d

$d$

x_{0} \oplus f_{n}

$x_0\oplus f_n$

A C_{d}^{0}

$AC^0_d$

C_{n} (x_{0}, \dots, x_{n})

$C_n(x_0,\dots,x_n)$

C_{n}

$C_n$

x_{0} = 1

$x_0=1$

A C_{d}^{0}

$AC^0_d$

\neg f_{n}

$\neg f_n$

A C_{d}^{0}

$AC^0_d$

f_{n}

$f_n$