Limites inférieures du circuit sur des ensembles arbitraires de portes

Dans les années 1980, Razborov a montré qu'il existait des fonctions booléennes monotones explicites (telles que la fonction CLIQUE) nécessitant de manière exponentielle de nombreuses portes ET et OU pour le calcul. Cependant, la base {AND, OR} sur le domaine booléen {0,1} n'est qu'un exemple d'un ensemble de portes intéressant qui n'est pas universel. Cela conduit à ma question:

Existe-t-il un autre ensemble de portes, intéressant de manière différente des portes monotones, pour lequel des limites inférieures exponentielles sur la taille du circuit sont connues (sans profondeur ni autre restriction sur le circuit)? Sinon, y a-t-il un autre ensemble de portes qui soit un candidat plausible pour de telles limites inférieures - des limites qui n'exigeraient pas nécessairement de franchir la barrière Natural Proofs, contrairement au résultat obtenu par les circuits monotones de Razborov?

Si un tel ensemble de portes existe, alors ce sera certainement sur un alphabet k-aire pour k≥3. La raison en est que, sur un alphabet binaire, le

(1) portes monotones ({AND, OR}),

(2) portes linéaires ({NOT, XOR}), et

(3) portes universelles ({AND, OR, NOT})

essentiellement épuiser les possibilités intéressantes, comme suit du théorème de classification de Post. (Notez que je suppose que les constantes --- 0 et 1 dans le cas binaire --- sont toujours disponibles gratuitement). Avec les portes linéaires, chaque fonction booléenne f: {0,1} ⁿ → {0,1} calculable du tout est calculable par un circuit de taille linéaire; avec un ensemble universel, nous sommes bien sûr confrontés aux Natural Proofs et aux autres barrières terrifiantes.

D'un autre côté, si nous considérons des jeux de portes sur un alphabet à 3 ou 4 symboles (par exemple), un ensemble plus large de possibilités s'ouvre - et à ma connaissance du moins, ces possibilités n'ont jamais été entièrement définies. du point de vue de la théorie de la complexité (corrigez-moi s'il vous plaît si je me trompe). Je sais que les jeux de portes possibles sont étudiés de manière approfondie sous le nom de "clones" en algèbre universelle; J'aimerais mieux connaître cette littérature afin de savoir ce que les résultats de cette zone signifient pour la complexité des circuits.

Dans tous les cas, il ne semble pas exclu qu'il existe d'autres limites dramatiques du circuit qui soient prêtes à être prouvées, si nous élargissons simplement la classe de jeux de portes sur des alphabets finis que nous sommes disposés à prendre en compte. Si je me trompe, dites-moi pourquoi!

(Déplacé des commentaires comme suggéré par Suresh. Notez que certaines erreurs dans le commentaire sont corrigées ici.)

Merci à Scott pour cette excellente question.

Scott semble suggérer que la difficulté des limites inférieures pourrait être due au langage restreint des opérations dans le cas booléen. L'argument de comptage de Shannon qui montre que la plupart des circuits doivent être grands repose sur l'écart entre une puissance d'expression dénombrable et un nombre incalculable de circuits. Cet écart semble disparaître lorsque l’alphabet comporte au moins 3 symboles.

Pour l'alphabet de taille 2 (cas booléen), le réseau de clones est infiniment infini et s'appelle le réseau de Post .

Le réseau de Post explique également pourquoi il n’ya que quelques bases d’opérations intéressantes pour le cas booléen.

Pour l'alphabet de taille 3 ou supérieure, le réseau des clones est indénombrable. De plus, le réseau ne satisfait aucune identité de réseau non triviale, il semble donc impossible de fournir une description complète du réseau. Pour un alphabet de taille 4 ou supérieure, le réseau de clones contient en réalité tous les réseaux finis sous forme de sous-réseau. Il existe donc une infinité de bases d’opérations éventuellement intéressantes à considérer lorsque l’alphabet comporte 3 symboles ou plus.

• Bulatov, Andrei A., Conditions remplies par des réseaux de clones , Algebra Universalis 46 237–241, 2001. doi: 10.1007 / PL00000340

Scott a demandé plus loin: le réseau de clones reste-t-il indénombrable si nous supposons que les constantes sont disponibles gratuitement?

La réponse est que oui, voir par exemple

• Gradimir Vojvodić, Jovanka Pantović et Ratko Tošić, Le nombre de clones contenant une fonction unaire , NSJOM 27 83–87, 1997. ( PDF )
• J. Pantović, R. Tošić et G. Vojvodić, La cardinalité des algèbres fonctionnelles complètes sur un ensemble de trois éléments , Algebra Universalis 38 136-140, 1997. doi: 10.1007 / s000120050042

bien qu'apparemment cela ait été publié plus tôt:

• Ágoston, I., Demetrovics, J. et Hannák, L. Sur le nombre de clones contenant toutes les constantes , Coll. Math. Soc. János Bolyai 43, 21-25, 1983.

Une belle déclaration spécifique est de:

• A. Bulatov, A. Krokhin, K. Safin et E. Sukhanov, Sur la structure des réseaux de clones , In: "Algèbre générale et mathématiques discrètes", rédacteurs: K. Denecke et O. Lueders, 27–34. Heldermann Verlag, Berlin, 1995. ( PS )

$k \ge 3$$\mathcal{L}_k$$2^{\aleph_0}$

Pour conclure, je ne suis au courant d'aucun travail sur l'utilisation de clones non booléens pour les limites inférieures du circuit. Cela semble mériter d’être approfondi. Compte tenu du peu de connaissances dont on dispose sur le réseau de clones, il peut exister des bases d’opérations intéressantes qui attendent d’être découvertes.

Davantage de liens entre la théorie des clones et l'informatique seraient probablement également d'un grand intérêt pour les mathématiciens travaillant en algèbre universelle. Un exemple précédent de ce type d'interaction est survenu lorsque Peter Jeavons a montré que les algèbres pouvaient être associées à des langages de contrainte, de manière à permettre la traduction des résultats de traçabilité en propriétés de l'algèbre. Andrei Bulatov a utilisé cela pour prouver la dichotomie des CSP avec la taille de domaine 3. En sens inverse, la théorie de la congruence apprivoisible a suscité un regain d'intérêt à la suite de l'application en informatique. Je me demande ce qui résulterait d'un lien entre la théorie des clones et la complexité des circuits non booléens.

Ceci est déplacé des commentaires, comme suggéré par Suresh.

$f:{0,1}^n \rightarrow {0,1}^n$$\Omega(\frac{n^2}{\log(n)})$

$\frac{n^2}{\log(n) * c}$$c$

$\Omega(n log n)$$\Omega(n^{3/2})$

Edit 2. L’obstacle principal est que nous n’avons aucune méthode pour prouver des limites inférieures non linéaires, même pour les portes linéaires, pour autant que je sache (pour les limites inférieures linéaires, on peut utiliser l’élimination de la porte, ce qui est très peu probable -lignes linéaires). Bien qu'il semble que certaines méthodes de l'algèbre linéaire doivent vraiment être utiles. Il est donc agréable de proposer des candidats, mais de nouvelles méthodes sont néanmoins nécessaires.

1. $\{0,1\}$$a$$Z_3^n=\{0,1,2\}^n$$\min(x,y)$$xy\mod{2}$$f(a)=0$$a$$0$$2$est dans est au moins le nombre de . Il montre que tout circuit (sur ce MIN / XOR) nécessite environ portes pour calculer . Mais c'était! Je ne suis au courant d'aucun autre résultat donnant lieu à une faveur similaire (aller vers des domaines plus grands, mais toujours finis), à l'exception, bien sûr, de la substance des circuits arithmétiques. Mais uniquement pour les circuits - pour les programmes de branchement allant à des domaines plus grands, facilite quelque peu la tâche des limites inférieures. $a$$1$$2^n/\sqrt{n}$$f$

2. Sur les circuits avec portes XOR. Ici, même le cas de la profondeur est largement ouvert. Les limites inférieures les plus élevées pour les transformations linéaires explicites sur ont la forme . Prouver une borne telle que pour une constante , même en profondeur et même si seules les portes XOR sont autorisées, relève du défi.$2$$y=Ax$$GF(2)$$n\log^{3/2}n$$n^{1+c}$$c>0$$2$