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

9

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{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:MODm

MODm(x1,,xk)={1 if xi0modm 0 if xi0modm 

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 MOD6 (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 MODm 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 ORMODm .

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

Gadi A
la source
1
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
1
Je suppose que , le nombre de variables d'entrée, est différent de , le module? nn
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

Réponses:

9

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.OUMOD

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?