Largeur d'arbre minimale du circuit pour MAJORITY

Quelle est la largeur d'arbre minimale d'un circuit sur pour calculer MAJ? $\{\wedge,\vee,\neg\}$

Ici MAJ $:\{0,1\}^n \rightarrow \{0,1\}$ sort 1 si au moins la moitié de ses entrées sont $1$ .

Je ne me soucie que de la taille du circuit (doit être polynomial) et qu'une entrée ne doit être lue qu'une seule fois bien que le fan-out d'une porte d'entrée puisse être arbitraire (cela affecte de manière cruciale la largeur d'arbre du circuit - la ramification les programmes obtenus à partir du théorème de Barrington du MAJ $\in$ $\mathsf{NC}^1$ , interprétés comme des circuits asymétriques, n'aident pas). Et bien sûr, la largeur de l'arbre est la chose la plus cruciale. Je me fiche de la profondeur ou de tout autre paramètre.

Certains des circuits communs pour MAJ comprennent:

Circuits d'arbre Wallace (par exemple le théorème 8.9 ici ) qui utilisent l'astuce 3-to-2 pour placer MAJ dans $\mathsf{NC}^1$ ?
Circuits monotones Valiant $\mathsf{NC}^1$ pour MAJ (par exemple Théorème 4 ici )
$\log^{O(1)}{n}$ profondeur réseau de tri tel que doseurs sorte
Réseau de tri AKS

Certains d'entre eux ont-ils une largeur d'arbre bornée ou même polylogarithmique?

Ou en fait,

Y a-t-il des raisons de croire qu'il n'y a pas de circuits bornés de largeur d'arbre pour MAJ?

Notez que chaque fonction calculée par un circuit de largeur d'arbre borné peut être calculée par un circuit $\mathsf{NC}^1$ même en l'absence de stipulation de lecture unique via JansenSarma . Ainsi, l'improbabilité d'une telle famille de circuits indiquerait que cette limite peut être encore resserrée dans le cas de circuits à lecture unique.

reference-request complexity-classes circuit-complexity treewidth SamiD
la source

Pourquoi n'est-ce pas trivial pour n'importe quelle langue ? Pour autant que je sache, les formules (c.-à-d. Les arbres) ont une largeur d'arbre de , ou ai-je raté quelque chose?

{N C}^{1}

$\mathrm{NC}^1$

1

$1$

Emil Jeřábek

Je pense que OP identifie toutes les feuilles de l'arbre de formule qui correspondent à la même variable, ce qui crée des cycles.

Sasho Nikolov

Un circuit à majorité peut être implémenté en arborescence O (log n). Le circuit simule simplement un algorithme en ligne qui lit un bit d'entrée à la fois et ajoute 1 à un nombre avec O (log n) bits si et seulement si l'entrée est 1. Notez que la profondeur du circuit est O (n). Voir la figure 1 de ( arxiv.org/pdf/1404.5565v1.pdf ). Un circuit de faible profondeur n'a pas nécessairement une petite largeur d'arbre car, comme l'a souligné Sasho Nikolov, vous devez identifier les nœuds correspondant à la même variable d'entrée.

Mateus de Oliveira Oliveira

@MateusdeOliveiraOliveira La construction que vous signalez est agréable et simple et correspond presque à ce dont j'ai besoin. Ce dont j'ai vraiment besoin, c'est d'une construction qui fonctionne dans une largeur d'arbre bornée (ou une indication pourquoi cela n'est pas possible). J'attendrai quelques jours pour voir s'il y a une autre réponse - sinon (si vous convertissez votre commentaire en réponse) je l'approuverai.

SamiD

@SamiD J'ai développé ce commentaire en une réponse. Je n'avais pas posté de réponse auparavant car ce n'est que la moitié de ce que vous avez demandé.

Mateus de Oliveira Oliveira

Réponses:

Répondre à la moitié de la question de Samir.

Soit soit un DAG et soit deux sous - ensembles de sommets de . On note l'ensemble de tous les fronts dans avec un point d'extrémité dans et un autre point d'extrémité dans . Si est un ordre total des sommets de alors nous laissons dénote la largeur de . La largeur en ligne de est définie comme $G=(V,E)$ $V_1,V_2\subseteq V$ $G$ $E(V_1,V_2)$ $G$ $V_1$ $V_2$ $\omega = (v_1,...,v_n)$ $G$

o w (G, ω) = max_{i} | E ({v_{1}, . . ., v_{i}}, {v_{i + 1}, . . ., v_{n}} |

$\mathbf{ow}(G,\omega) = \max_{i}\; |E(\{v_1,...,v_i\},\{v_{i+1},...,v_n\}|$

ω

$\omega$

G

$G$

o w (G) = min_{ω} o w (G, ω),

$\mathbf{ow}(G) = \min_{\omega}\; \mathbf{ow}(G,\omega),$ où le minimum est pris en charge tous les ordonnancements topologiques des sommets du . Notez que la notion traditionnelle de largeur de coupe de , est définie de manière analogue, sauf que le minimum est pris en compte dans tous les ordres possibles de , indépendamment du fait que l'ordre soit topologique ou non. Nous avons la séquence d'inégalités suivante: où et sont respectivement les pathwidth et la largeur arborescente de .

G

$G$

G

$G$

c w (G)

$\mathbf{cw}(G)$

G

$G$

t w (G) \leq p w (G) \leq c w (G) \leq o w (G),

$\mathbf{tw}(G) \leq \mathbf{pw}(G) \leq \mathbf{cw}(G)\leq \mathbf{ow}(G),$

p w (G)

$\mathbf{pw}(G)$

t w (G)

$\mathbf{tw}(G)$

G

$G$

Nous affirmons que la MAJORITÉ de bits peut être calculée dans la largeur en ligne , et donc dans la largeur d'arbre . Le circuit simule un algorithme en ligne qui lit un bit d'entrée à la fois et ajoute à un compteur avec bits si et seulement si . Au début, le compteur est initialisé à $n$ $O(\log n)$ $O(\log n)$ $b$ $b$ $O(\log n)$ $b=1$ $0$ . A la fin le circuit accepte si et seulement si la valeur du compteur est supérieure à n / 2. Il est facile de voir que les portes d'un circuit ADD qui en ajoute un au registre de compteur peuvent être ordonnées topologiquement de telle sorte qu'il ait une largeur en ligne constante, car ces circuits ont juste besoin de mettre en œuvre une opération de poursuite. Le circuit total est une séquence de circuits où la sortie de est connectée à l'entrée de et la sortie de est connectée à la entrée de COMP. Maintenant, si nous topologiquement le circuit total de telle manière que toutes les portes de apparaissent avant les portes de et toutes les portes de $C=(ADD_1,ADD_2,...,ADD_n,COMP)$ $ADD_i$ $ADD_{i+1}$ $ADD_n$ $C$ $ADD_i$ $ADD_{i+1}$ $ADD_n$ apparaît devant les portes de COMP, alors cet ordre topologique a une largeur en ligne . Cette construction est illustrée sur la figure 1 d' un de mes articles pour montrer que l'amplification des probabilités peut être effectuée en largeur logarithmique en ligne. $O(\log n)$

Obs: La profondeur du circuit C est . $O(n)$

Mateus de Oliveira Oliveira
la source

En remarque, faire le même circuit mais comme un arbre binaire (avec la sortie à la racine) plutôt qu'un chemin donne un circuit avec la largeur d'arbre O (log n) et la profondeur O (log n)

daniello

Il semble qu'une traduction directe en arbres donnerait la profondeur O ((log n) ^ 2) puisque nous aurions besoin de la profondeur O (log n) pour chaque additionneur. Mais il est vrai que l'arborescence serait O (log n).

Mateus de Oliveira Oliveira

Bien sûr, vous avez raison, merci! Il semble que si les ajouts sont implémentés en tant que DNF, nous obtenons alors la largeur et la profondeur de l'arbre O (log n), mais la taille .

O (n^{3})

$O(n^3)$

daniello

le fait de représenter l'additionneur en tant que DNF est qu'il peut potentiellement augmenter la largeur de l'arborescence, car maintenant chaque variable sera partagée avec (à première vue de manière polynomiale) de nombreuses clauses. Votre suggestion de réduire la profondeur à O (log n) fonctionnerait si vous pouvez montrer que l'ajout de deux nombres avec des bits O (log n) peut être effectué en profondeur constante et en largeur d'arbre logarithmique.

Mateus de Oliveira Oliveira

Eh bien - pour toute fonction booléenne sur bit d'entrée et bit de sortie le DNF a une profondeur , une taille et une largeur d'arbre car la suppression des portes d'entrée + sortie laisse un ensemble indépendant ...

a

$a$

b

$b$

2

$2$

2^{a} + a + b

$2^a + a + b$

\leq a + b

$\leq a+b$

daniello

Répondre à l'autre moitié de la question - voici un croquis de preuve pour une borne inférieure pour la largeur d'arbre pour une constante . La limite est indépendante de la taille ou de tout autre aspect du circuit. Dans le reste de l'argument est le circuit, est la largeur d'arbre de et est le nombre de portes d'entrée. $c \cdot \log n$ $c$ $C$ $t$ $C$ $n$

La première étape consiste à utiliser le lemme de séparateur équilibré pour les graphiques de largeur d'arbre bornée . Les portes (y compris les portes d'entrée) du circuit peuvent être divisées en trois parties , et , de sorte que et et contiennent au moinsdes portes d'entrée, et il n'y a pas d' arcs (fils) entre et . $L$ $R$ $S$ $|S| \leq t+1$ $L$ $R$ $n/3-|S|$ $L$ $R$

Dans le reste de la preuve, la seule propriété du circuit que nous utiliserons est ce partitionnement - donc la preuve donne en fait une limite inférieure sur la taille d'un séparateur équilibré comme ci-dessus. $S$

Ayant à portée de main, nous construisons un circuit partir de comme suit: pour chaque porte dans faites deux portes et , et faisons et alimenter en . Pour tous les fils menant à de faites-les plutôt passer à . Pour tous les fils menant à de faites-les plutôt passer à . Soit $(L,S,R)$ $C'$ $C$ $g$ $S$ $g_L$ $g_R$ $g_L$ $g_R$ $g$ $g$ $L$ $g_L$ $g$ $R$ $g_R$

S^{'} = {g, g_{L}, g_{R} : g \in S} .

$S' = \{g, g_L, g_R : g \in S\}.$

Pour chacune des affectations à créez un circuit qui produit 1 si (a) l'affectation aux portes d'entrée rend sortie vraie et (b) l'affectation aux portes d'entrée définit tous les portes de comme deviné. Appelez ces circuits , , pour . A noter que le circuit se décompose naturellement en deux sous- circuits et tels que ne dépend que des portes d'entrée de , ne dépend que des portes d'entrée de $2^{|S'|}$ $S'$ $C'$ $S'$ $C_1$ $C_2$ $C_3 \ldots C_x$ $x \leq 8^t$ $C_i$ $C_i^L$ $C_i^R$ $C_i^L$ $L \cup S'$ $C_i^R$ $R \cup S'$ , et pour chaque affectation aux portes d'entrée , nous avons que . $C_i = C_i^L \wedge C_i^R$

Puisque chaque affectation aux portes d'entrée est cohérente avec une certaine estimation de ce qui se passe dans nous avons que . Ainsi, nous avons réécrit le circuit comme un OU (de fanin ) de ET (de fanin ) où le numéro de porte ET est alimenté en sortie de et respectivement. $S'$ $C' = C_1 \vee C_2 \vee C_3 \ldots \vee C_x$ $C$ $8^t$ $2$ $i$ $C_i^L$ $C_i^R$

Soit l'ensemble des portes ET les plus hautes. Nous allons d'abord prouver que. Cela donne un simple borne inférieure sur . Nous prouverons alors une meilleure limite. $Z$ $2^{|Z|} \geq n/3-|S|$ $\log \log n$ $t$

Supposons queEt supposer sans perte de généralité que contient moins de portes d'entrée que . Alors et contiennent au moinsportes d'entrée. Selon le principe du pigeon, il y a deux nombres différents et tels qu'il y a deux affectations différentes aux portes d'entrée de , celle qui définit les portes à vrai, celle qui définit , de sorte que les circuits , produisent tous la même chose. Mais il existe une affectation aux portes d'entrée dans $2^{|Z|} < n/3-|S|$ $L$ $R$ $L$ $R$ $n/3-|S|$ $i$ $j$ $L$ $i$ $j$ $C_1^L$ $C_2^L \ldots C_x^L$ $R$ de telle sorte que MAJORITY délivre FALSE si gates dans sont définies sur true et MAJORITY sort TRUE si gates dans sont définies sur true. Ceci est une contradiction et donc ce qui implique que l'arborescence est au moins . $i$ $L$ $j$ $L$ $2^{|Z|} \geq n/3-|S|$ $\log \log n$

Nous montrons maintenant une meilleure limite:. On suppose que wlog contient moins de portes d'entrée que . Alors L et R contiennent au moinsportes d'entrée. Considérez l'affectation « tout faux » à . Soit le plus petit nombre de portes d'entrée de qui doit être mis à vrai de telle sorte que MAJ génère VRAI, étant donné que tout est mis à faux. $|Z| \geq n/3-|S|$ $L$ $R$ $n/3-|S|$ $L$ $r$ $R$ $L$

Depuis la mise à tous faux et exactement portes d' entrée de à sortie véritables marques MAJORITÉ il doit y avoir un tel que sorties TRUE, WLOG cela est . Toutes les affectations à avec moins de vraies portes d'entrée doivent définir sur false. Étant donné que le réglage de porte d'entrée de sur vrai et les portes d'entrée de sur vrai rendent la sortie MAJORITÉ , le réglage de porte de sur vrai doit faire au moins un $L$ $r$ $R$ $1$ $i$ $C_i^L$ $C_1^L$ $R$ $r$ $C_1^R$ $1$ $L$ $r-1$ $R$ $1$ $1$ $L$ $C_i^L$ outpur true pour . wlog on peut supposer que . Ensuite, toutes les affectations à qui définissent au plus portes d'entrée sur true doivent définir sur false, et ainsi de suite - nous pouvons répéter cet argument fois. Mais cela signifie que, donnant une limite inférieure pour . $i \neq 1$ $i=2$ $R$ $r-2$ $C_2^R$ $r$ $|Z| \geq r \geq n/3-|S|$ $c \cdot \log n$ $t$

[Je suis conscient que ce croquis devient un peu ondulé à la main à certains endroits, demandez si quelque chose n'est pas clair ...]

daniello
la source