L'addition peut-elle être effectuée en moins de la profondeur 5?

En utilisant l'algorithme de report prospectif, nous pouvons calculer l'addition en utilisant une profondeur de taille polynomiale 5 (ou 4?) famille de circuits . Est-il possible de réduire la profondeur? Peut-on calculer l'addition de deux nombres binaires en utilisant une famille de circuits de taille polynomiale avec une profondeur inférieure à celle obtenue par l'algorithme de report prospectif? $AC^0$

Existe-t-il des bornes inférieures super polynomiales pour la taille des familles de circuits calculant l'addition où est 2 ou 3? $AC^0_d$ $d$

Par profondeur, j'entends la profondeur d'alternance.

cc.complexity-theory circuit-complexity lower-bounds upper-bounds Anonyme
la source

Peux-tu nous dire ton nom? Qui tu es? Au cours du mois dernier, les gens créent un nouveau nom d'utilisateur ici, posent une question, puis suppriment ce nom d'utilisateur!

Tayfun Pay

@Geekster, les gens ne sont généralement pas tenus de créer un compte ou d'utiliser leur vrai nom (mais il est encouragé de le faire pour diverses raisons). Si vous avez une préoccupation générale à propos de quelque chose, veuillez utiliser la méta informatique théorique pour la soulever.

Kaveh

Cela pourrait être forcé brutalement en vérifiant qu'aucun circuit de profondeur

ne peut calculer la somme

bits de deux entrées

bits pour certains

fixes ; il n'y a qu'un nombre fini de fonctions booléennes des bits d'entrée qui peuvent apparaître à chaque profondeur.

4

$4$

^{0}

$^{0}$

(m + 1)

$(m+1)$

m

$m$

m

$m$

mjqxxxx

@mjqxxxx: Comment appliquez-vous la contrainte de taille polynomiale sur les circuits AC0 lors du forçage brut pour un m fixe? @ OP: La meilleure profondeur de circuit actuelle 4 ou 5 est-elle la meilleure?

Robin Kothari

@mjqxxxx: Chaque fonction booléenne est calculable par des circuits de profondeur

. Supposons maintenant que vous trouviez pour votre

fixe un circuit de taille

. Comment jugez-vous s'il existe des circuits de taille

pour chaque

, où

, ou s'il existe uniquement des circuits de taille

, où

? Il n'y a tout simplement aucun moyen de déduire des informations asymptotiques à partir d'un exemple fini.

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 soutient Monica

Réponses:

Selon le théorème 3.1 dans Alexis Maciel et Denis Therien Threshold Circuits of Small Majority-Depth, il existe en effet un circuit de profondeur 3 pour calculer l'addition de deux nombres.

La limite précise est où sont des problèmes qui ont la profondeur 2 circuits à la fois portes en haut et en circuits sont circuits de profondeur un (voir l'article pour une explication détaillée de la notation). $\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$

Les principales idées de preuve sont:

Tout d'abord, exprimez le circuit d'anticipation Carry comme $\mathsf{NC}^0\cdot\Delta_2\cdot\mathsf{NC}^0$
Ensuite, invoquez les propriétés de fermeture de pour écrire ceci comme $\Delta_2$ $\Delta_2\cdot\mathsf{NC}^0$
Enfin, utilisez le fait (également prouvé dans l'article) que $\mathsf{NC}^0 \subset \Delta_1\cdot\mathsf{NC}^0_1$

SamiD
la source

Les circuits de profondeur 2 nécessitent une taille exponentielle pour calculer l'addition, car un circuit de profondeur 2 doit être DNF ou CNF et il est facile de vérifier qu'il existe de manière exponentielle de nombreux minterms et maxterms.

Attention : la partie ci-dessous est buggée . Voir les commentaires sous la réponse.

De la façon dont je le compte, l'addition peut être effectuée en profondeur 3. Supposons et sont les ème bits des deux nombres, où est l'indice du LSB et du MSB. $a_i$ $b_i$ $i$ $0$ $n$

Calculons le ème bit de la somme, de la manière standard avec report d'anticipation: $i$ $s_i$

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

$s_i = a_i \oplus b_i \oplus c_i$

où est XOR et est le portage calculé comme suit: $\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)$

et signifie que le ème emplacement "a généré" le report: $g_j$ $j$

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

$g_j = (a_j \wedge b_j)$

et signifie que le report se propage de à : $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)$

En comptant la profondeur, est la profondeur 2 et est la profondeur 3. Alors qu'il semblerait que soit la profondeur 4 ou 5, ce n'est vraiment que la profondeur 3 car il s'agit d'un calcul fanin borné de circuits de profondeur 3 donc un peut pousser les deux niveaux supérieurs vers le bas en utilisant des formules de-Morgan, tout en gonflant la taille du circuit d'une quantité polynomiale. $p_j$ $c_i$ $s_i$

Noam
la source

Je ne vois pas exactement comment le calcul fanin borné des circuits de profondeur 3 est automatiquement de profondeur 3. Si, disons, vous écrivez

comme

, vous pouvez faire le premier disjoncté un circuit de profondeur 3 avec

en haut, et le second disjoncté un circuit de profondeur 3 avec

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$ en haut. Je ne vois pas comment pousser la disjonction supérieure vers le bas sans augmenter la profondeur d'un pour tenir compte de l'inadéquation entre les types conjonctifs dans les deux parties. Cela peut être résolu en notant que

peut également être calculé de manière différente par un circuit de profondeur 3 ...

c_{i}

$c_i$

Emil Jeřábek soutient Monica

... avec

sur le dessus. D'un autre côté, tous les circuits de profondeur 3 ont borné le fan-in inférieur, donc je les appellerais profondeur 2 1/2.

⋀

$\bigwedge$

Emil Jeřábek soutient Monica

Cela est évident. Ce que je signale, c'est que tel qu'écrit, vous n'avez pas ici un OU de deux circuits de profondeur

avec ET sur le dessus. Vous avez un OU de deux circuits de profondeur

, dont l'un a ET sur le dessus, et l'autre a OU sur le dessus. Je doute que de tels circuits puissent être convertis en profondeur

en général. Considérez les AND et OR polynomiaux en éventail comme des quantificateurs. Vous pouvez exprimer

d

$d$

d

$d$

d

$d$

comme formule prénex avec

blocs de quantification, mais vous avez besoin de

blocs pour exprimer ...

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

Emil Jeřábek soutient Monica

... la formule

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

Emil Jeřábek soutient Monica

Pour un contre-exemple explicite du principe général, soit

une famille de fonctions calculables par

circuits avec OR en haut nécessitant des circuits super-polynomiaux de profondeur

avec ET en haut (par exemple, les fonctions Sipser). Alors

n'ont pas de circuits

. Supposons pour contradiction que

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)$ sont de tels circuits, et que

a OR sur le dessus (l'autre cas est symétrique). En fixant

, on obtient

circuits pour

avec OR en haut, d'où

circuits pour

avec AND en haut, une contradiction.

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$

Emil Jeřábek soutient Monica