Les circuits de profondeur 2 avec portes OR et MOD ne sont pas universels?

Il est bien connu que chaque fonction booléenne peut être réalisée en utilisant un circuit booléen de profondeur 2 (sur les variables, leur négation et leurs valeurs constantes) contenant des portes ET au premier niveau et une seule porte OU au niveau supérieur; c'est simplement la représentation DNF de . $f:\{0,1\}^n\to \{0,1\}$ $f$

Un autre type de porte qui présente un grand intérêt pour la complexité du circuit est la porte . La définition habituelle est la suivante: $MOD_m$

{M O D}_{m} (x_{1}, \dots, x_{k}) = {\begin{cases} 1 & if \sum x_{i} \equiv 0 \mod m \\ 0 & if \sum x_{i} ≢ 0 \mod m \end{cases}

$\mathrm{MOD}_m(x_1,\dots,x_k)=\cases{ 1 & if $\sum x_i \equiv 0 \mod m$ \\ 0 & if $\sum x_i \not\equiv 0 \mod m$ \\ }$

Ces portes ont parfois un pouvoir surprenant; par exemple, toute fonction booléenne peut être représentée par un circuit de profondeur 2 ayant seulement des portes $\mathrm{MOD}_6$ (c'est du folklore mais je peux élaborer si quelqu'un est intéressé).

Cependant, un autre folklore est que les circuits avec une seule porte OU en haut et des portes $\mathrm{MOD}_m$ dans la couche inférieure (avec $m$ étant fixé une fois pour toutes, et en particulier étant le même pour toutes les portes) ne sont pas universel, c'est-à-dire que pour toute valeur de $m$ , il existe des fonctions booléennes qui ne peuvent pas être calculées par le circuit $\mathrm{OR} \circ \mathrm{MOD}_m$ .

Je cherche une preuve pour cette affirmation, ou au moins une direction.

complexity-theory logic circuits Gadi A
la source

Dans le premier paragraphe, soit vous n'avez PAS besoin de portes, soit vous devez dire «toutes les fonctions booléennes monotones ».

Tsuyoshi Ito

Vous avez raison; l'hypothèse habituelle est que vous avez en entrée les variables, leur négation et aussi des valeurs arbitraires (importantes pour les modgates). Je vais écrire cela explicitement.

Gadi A

Je suppose que , le nombre de variables d'entrée, est différent de , le module?

n

$n$

n

$n$

Kristoffer Arnsfelt Hansen

Oui, désolé.

Gadi A

Cela m'intéresse. Connaissez-vous une référence pour le premier fait folklorique? Je me demande, si dans la dernière classe de circuits vous autorisez seulement un OU, combien autorisez-vous dans le premier?

Juan Bermejo Vega

La fonction booléenne AND ne peut pas être calculée. Supposons en fait que la fonction ET soit calculée par un circuit . Il s'ensuit alors que l'un des sous-circuits MOD doit déjà calculer ET fonctionne déjà, ce qui est impossible. $\text{OR} \circ \text{MOD}$

Kristoffer Arnsfelt Hansen
la source

Non, il a raison. L'hypothèse implicite ici est que n est constant et nous devrions être capables de gérer un nombre arbitrairement élevé d'entrées avec des portes mod_n.

Gadi A

@GadiA Ah, ok. Ce n'était pas clair dans votre question, du moins pour les personnes qui ne connaissent pas le domaine. J'ai fait une modification mineure qui devrait clarifier cela.

Gilles 'SO- arrête d'être méchant'

Oui, ma question était très mal formulée, désolé.

Gadi A

@Gilles Pouvez-vous m'expliquer quel fan-in ici nous considérons? Le problème pour moi est que je ne vois pas pourquoi le sous-circuit de MOD ne peut pas calculer ET? Combien d'entrées a ce MOD et ce ET?

Les circuits de profondeur 2 avec portes OR et MOD ne sont pas universels?

Réponses: