PARITÉ

$AC^0$ est la classe des circuits de taille polynomiale à profondeur constante avec portes NON et portes fan-in ET et OR sans limite, où les entrées et les portes ont également une fanout sans limite.

Considérons maintenant une nouvelle classe, appelons-la $AC^0_{bf}$ qui est comme $AC^0$ mais pour laquelle les entrées et les portes ont au maximum $O(1)$ . Cette classe est clairement en $AC^0$ . En fait, il est strictement contenu dans $AC^0$ , comme indiqué ici . Par conséquent, PARITY n'est évidemment pas dans $AC^0_{bf}$ .

Existe-t-il une preuve de PARITE qui ne passe pas également pour ? En d'autres termes, existe-t-il une preuve qui n'utilise pas de techniques puissantes comme le lemme de commutation ou la méthode Razborov / Smolensky? $\notin AC^0_{bf}$ $AC^0$

cc.complexity-theory circuit-complexity Adam Paetznick
la source

Cela s'appelle

dans la littérature: qwiki.stanford.edu/index.php/Complexity_Zoo:N#nc0

{N C}^{0}

$\mathsf{NC}^0$

Hsien-Chih Chang 之之

Non, ce n'est pas le cas, car le fanin est illimité.

domotorp

Ah, j'ai mal lu le mot fanout. Merci de l'avoir signalé.

Hsien-Chih Chang 張顯之

Article connexe de @Kaveh: cstheory.stackexchange.com/q/1824/1800 , déplacé des commentaires ci-dessous pour augmenter l'exposition.

Hsien-Chih Chang 張顯之

Qu'est-ce que le «fanout borné», au fait?

xxx ---

Réponses:

Je pourrais manquer quelque chose, mais n'est-il pas la même chose qu'une formule? Étant donné que chaque bit d'entrée peut avoir un effet sur au plus un nombre limité de portes, nous pouvons simplement supposer que chaque porte n'a qu'une seule sortie (après avoir peut-être dupliqué quelques éléments) et nous pouvons également abaisser les portes non. Nous savons que la taille de la formule de la parité est n ^ 2 (voir Troy J. Lee, " La taille de la formule de la PARITÉ ", 2007) et puisque à chaque niveau de notre circuit, nous ne pouvons avoir que des portes O (n), cela montre que la parité n'est pas dans . $AC^0_{bf}$ $AC^0_{bf}$

domotorp
la source

donc par "Formule" vous voulez dire une formule de taille linéaire, non? et par taille, vous voulez dire la taille de la formule ...

Alessandro Cosentino

Je pense que votre réponse est correcte à la fin, mais le raisonnement est plus subtil. Le fanout de la porte peut être réduit en dupliquant des parties du circuit, mais cela augmente la taille de la formule. (La taille de la formule équivaut au nombre de fils d'entrée.) Supposons que le fanout de la porte soit au maximum 2. Ensuite, pour réduire le fanout des portes de la couche inférieure, je dois dupliquer chaque porte et chaque entrée, doublant ainsi la taille de la formule. La répétition de ce processus pour chaque couche donne une formule de taille

où

est la profondeur du circuit. Dans notre cas,

est une constante, la taille de la formule est donc toujours linéaire.

O (2^{d} n)

$O(2^dn)$

d

$d$

d

$d$

Adam Paetznick

C'était exactement ce que je voulais dire, désolé si mon exposition était médiocre.

domotorp

@Alessandro: Je suis désolé si j'ai mal compris votre question. Mais ma première impression est que l'on peut transformer n'importe quel circuit de profondeur-d de taille en uneformule deprofondeur d(fanout 1) de taille environ : il suffit de procéder couche par couche en partant du bas (à côté des entrées) couche, et prendre plusieurs copies de la même porte; à chaque couche le nombre de portes peut augmenter au maximum le facteur de . Cela signifie que toute limite inférieure pour lesformules implique une limite inférieure pour lescircuits $S$ $S^d$ $S$ $S$ $AC^0$ $S^{1/d}$ $AC^0$ . Il est donc difficile de s'attendre à des preuves de borne inférieure plus faciles pour les formules : dans le monde , est une constante. $AC^0$ $AC^0$ $d$

Btw votre langue (chaînes avec exactement un ) a une DNF triviale ( formule de profondeur 2 ) avec monômes. $X$ $1$ $n$

Stasys
la source

S^{d}

$S^d$

k^{d} S

$k^dS$

k

$k$

S

$S$

Une autre façon de voir que

est strictement contenu dans

est de noter que puisque chaque bit d'entrée a un fanout au plus k, il y a au plus

portes dans la première couche, et

A C_{b f}^{0}

$AC^0_{bf}$

A C^{0}

$AC^0$

k n

$kn$

k^{2} n

$k^2n$

O (n)

$O(n)$

A C^{0}

$AC^0$

A C_{b f}^{0}

$AC^0_{bf}$

Quelqu'un peut-il me dire pourquoi ce modèle "pas plus de k copies d'une variable d'entrée" est intéressant? Même lorsque la profondeur est constante. Dans quel contexte un tel modèle se pose-t-il? Suis juste curieux.

Stasys

Q A C^{0}

$QAC^0$

@Adam: Merci, en effet, domotorp a déjà mentionné un non

A C^{0}

$AC^0$

n \log n

$n\log n$