Quelle est la taille d'un circuit booléen en couches pour une fonction avec une complexité de circuit

Considérons une fonction calculée par un circuit booléen avec entrées de taille sur la base (avec indegree 2 pour le portes). $f$ $C$ $n$ $s(n) = \mathsf{poly}(n)$ $\{\mathsf{XOR},\mathsf{AND},\mathsf{NOT}\}$ $\mathsf{XOR},\mathsf{AND}$

Un circuit booléen est en couches s'il peut être disposé en couches ( étant la profondeur du circuit) de portes de sorte que tout bord entre deux portes relie les couches adjacentes. $d$ $d$

Étant donné que a un circuit booléen de taille , que pouvons-nous dire de la taille d'un circuit en couches calculant ? Il y a une limite supérieure triviale: en ajoutant des nœuds factices à à chaque couche traversée par un bord, nous obtenons un circuit en couches de taille au plus . Mais pouvons-nous nous améliorer en général (par exemple ou ), ou pour une classe de circuits intéressante? $f$ $s$ $f$ $C$ $O(s^2)$ $O(s\cdot \log s)$ $O(s)$

Contexte. Cette question découle de résultats récents en cryptographie qui montrent comment calculer en toute sécurité des circuits booléens en couches de taille avec communication (par exemple ou ; J'essaie de comprendre à quel point cette restriction aux circuits booléens en couches peut être restrictive dans la pratique, que ce soit pour les circuits généraux ou pour les circuits "naturels". Cependant, je n'ai pas trouvé grand-chose sur les circuits en couches dans la littérature; des indications appropriées seraient également les bienvenues. $s$ $o(s)$ $s/\log s$ $s/\log\log s)$

circuit-complexity circuits Geoffroy Couteau
la source

Voici un exemple d'un circuit qui semble difficile à convertir en un circuit en couches sans une augmentation significative de la taille. Définissez

pour être une fonction qui peut être calculée en taille

. Définissez

f : {0, 1}^{n - 1} \to {0, 1}

$f:\{0,1\}^{n-1} \to \{0,1\}$

u

$u$

, et que

soit

itérations de

. Alors

a la taille

. Il semble difficile de construire un circuit en couches avec une taille inférieure à

. Donc, si

, nous devrions peut-être nous attendre à un écart entre la taille d'un circuit et la taille d'un circuit en couches. Pas une preuve, juste un exemple suggestif pour peut-être conduire l'intuition.

g (x_{1}, \dots, x_{n}) = (x_{2}, \dots, x_{n}, x_{1} \oplus f (x_{2}, \dots, x_{n}))

$g(x_1,\dots,x_n) = (x_2,\dots,x_n,x_1 \oplus f(x_2,\dots,x_n))$

C

$C$

t

$t$

g

$g$

C

$C$

O (t u)

$O(tu)$

Θ (n t)

$\Theta(nt)$

u = o (n)

$u=o(n)$

Pour autant que je m'en souvienne, pour les circuits en couches, la borne inférieure la plus connue est de la forme

. Il est particulièrement facile à prouver pour une fonction

to-

. Prenons, par exemple, une carte linéaire

où

a des zéros uniquement sur la diagonale principale. Ensuite, il doit avoir au moins

portes sur chaque couche et le nombre de couches est d'au moins

. Notez que cette fonction peut être facilement calculée par un circuit régulier de taille

Ω (n \log n)

$\Omega(n \log n)$

n

$n$

n

$n$

A x

$Ax$

A \in {0, 1}^{n \times n}

$A \in \{0,1\}^{n \times n}$

n

$n$

\log_{2} n

$\log_2 n$

. Pour les fonctions à sortie unique, il est également possible de prouver la même limite inférieure, mais je ne me souviens pas de l'argument.

O (n)

$O(n)$

Alexander S.Kulikov

Merci beaucoup pour les commentaires. @ AlexanderS.Kulikov, est votre argument folklore, ou avez-vous un pointeur vers des œuvres sur des circuits en couches? Le

est logique - j'aurais été très surpris par quelque chose de plus petit - mais

la seule borne supérieure connue?

Ω (n \log n)

$\Omega(n \log n)$

O (n^{2})

$O(n^2)$

Geoffroy Couteau

Je suppose que c'est un folklore, oui. Je ne suis pas sûr d'avoir la question sur la limite supérieure de

. Vous voudrez peut-être jeter un œil à l'article suivant: cs.utexas.edu/~panni/sizedepth.pdf

O (n^{2})

$O(n^2)$

Alexander S. Kulikov

Je pense que nous ne connaissons pas de transformation meilleure que

en général. Notez qu'un circuit de taille

et de profondeur

peut être transformé en un circuit en couches de taille au plus

. (Ce qui, dans le pire des cas, nous donne un circuit de taille

.) Je voulais juste souligner que si nous pouvions prouver une limite inférieure de

sur la taille d'un circuit en couches, ce serait nous donner une borne inférieure super-linéaire sur la taille des circuits de profondeur de log pour cette fonction. Cette question reste ouverte depuis plus de 40 ans.

O (s^{2})

$O(s^2)$

s

$s$

d

$d$

d s

$ds$

O (s^{2})

$O(s^2)$

ω (n \log n)

$\omega(n\log{n})$

Alex Golovnev

Pour autant que je sache, trois classes de circuits en couches ont été étudiées. Dans toutes ces définitions, les arcs sont autorisés uniquement entre deux couches adjacentes.

Un circuit est appelé synchrone ( Harper 1977 ) si toutes les portes sont disposées en couches, et les entrées doivent être au niveau 0. (Une définition équivalente: pour toute porte $g$ , tous les chemins des entrées vers $g$ ont la même longueur.)
Un circuit est localement synchrone ( Belaga 1984 ) si chaque entrée se produit exactement une fois mais sur une couche arbitraire.
$g$ $o$ $g$ $o$

Il est facile de voir que les trois classes sont répertoriées du plus faible au plus fort (et la classe des circuits sans restriction est encore plus forte).

$s$

$s$ $s^2$
$\omega(s\log{s})$ $s$ $d$ $O(sd)$ $f$ $\omega(n\log{n})$ $f$ $O(\log{n})$ $O(n)$
Il existe des fonctions explicites

$\Omega(n\log{n})$ $O(n)$

$\Omega(n\log{n})$ $O(n)$

$n$

$f\colon\{0,1\}^n\to\{0,1\}^n$ $i$ $i$ $O(n)$ $\log{n}$ $n$ $n$ $f$ $\Omega(n\log{n})$ $n-1$ $\Omega(\log{n})$ $n$ $n$

Alex Golovnev
la source

Quelle est la taille d'un circuit booléen en couches pour une fonction avec une complexité de circuit

Réponses: