A adição pode ser realizada em menos de profundidade 5?

Usando o algoritmo carry look ahead, podemos calcular a adição usando uma profundidade de tamanho polinomial 5 (ou 4?) família de circuitos . É possível reduzir a profundidade? Podemos calcular a adição de dois números binários usando uma família de circuitos de tamanho polinomial com profundidade menor que a obtida pelo algoritmo carry look ahead? $AC^0$

Existem limites inferiores super polinomiais para o tamanho das famílias de circuitos que computam a adição em que é 2 ou 3? $AC^0_d$ $d$

Por profundidade, quero dizer profundidade de alternância.

cc.complexity-theory circuit-complexity lower-bounds upper-bounds Anônimo
fonte

Você pode nos dizer seu nome? Quem é você? Nos últimos meses, as pessoas criaram um novo nome de usuário aqui, fazendo uma pergunta e excluindo esse nome de usuário!

Tayfun Pay

@Geekster, geralmente as pessoas não precisam criar uma conta ou usar seus nomes reais (no entanto, é recomendável fazê-lo por várias razões). Se você tem uma preocupação geral com alguma coisa, use o Meta da Ciência da Computação Teórica para levantá-la.

Kaveh

Isso pode ser forçado com brutalidade, verificando que nenhum circuito de profundidade -

pode calcular a soma

bits de duas entradas de

bits para algum

fixo ; existem apenas muitas funções booleanas finitas dos bits de entrada que podem aparecer a cada profundidade.

4

$4$

^{0}

$^{0}$

(m + 1)

$(m+1)$

m

$m$

m

$m$

Mjqxxxx

@mjqxxxx: Como você impõe a restrição de tamanho polinomial nos circuitos AC0 quando força bruta para um m fixo? @ OP: A melhor profundidade do circuito atual é 4 ou 5?

Robin Kothari

@mjqxxxx: Toda função booleana é computável por circuitos de profundidade

. Agora, suponha que você encontrar para o seu fixo

um circuito de tamanho

. Como você julga se existem circuitos de tamanho

para cada

, onde

, ou se existem apenas circuitos de tamanho

, onde

? Simplesmente não há como inferir informações assintóticas a partir de um exemplo 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 apoia Monica

Respostas:

De acordo com o Teorema 3.1 de Alexis Maciel e Denis Therien Threshold Circuits of Small Majority-Depth, existe de fato um circuito de profundidade 3 para calcular a adição de dois números.

A preciso ligado é onde são problemas que têm profundidade-2 circuitos com ambos portas na parte superior e circuitos são circuitos profundidade um (veja o artigo para uma explicação detalhada da notação). $\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$

As principais idéias de prova são:

Em primeiro lugar, expressar o circuito Carry-verificação à frente como $\mathsf{NC}^0\cdot\Delta_2\cdot\mathsf{NC}^0$
Em seguida, invoque as propriedades de fechamento de para escrever isso como $\Delta_2$ $\Delta_2\cdot\mathsf{NC}^0$
Finalmente, a utilização do fato (também se mostrou no papel) que $\mathsf{NC}^0 \subset \Delta_1\cdot\mathsf{NC}^0_1$

SamiD
fonte

Os circuitos de profundidade 2 exigem tamanho exponencial para calcular a adição, pois um circuito de profundidade 2 deve ser DNF ou CNF e é fácil verificar se existem exterencialmente muitos mintermos e maxtermos.

Atenção : a parte abaixo é de buggy . Veja os comentários sob a resposta.

$a_i$ $b_i$ $i$ $0$ $n$

$i$ $s_i$

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

$s_i = a_i \oplus b_i \oplus c_i$

$\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)$

$g_j$ $j$

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

$g_j = (a_j \wedge b_j)$

$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
fonte

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$