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

40

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} n → {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!

Scott Aaronson
la source
3
Si vous considérez les fonctions , la situation est plus complexe pour les portes linéaires, car l'argument de comptage indique qu'il existe des fonctions nécessitant gates à calculer, bien que je sache, il n’existe pas d’exemples explicites de fonctions nécessitant des circuits de taille superlinéaire. Ω ( n 2f:{0,1}n{0,1}nΩ(n2log(n))
Grigory Yaroslavtsev
2
Remarque: si vous remplacez les portes booléennes monotones par des portes qui calculent les fonctions réelles non décroissantes , vous obtenez également des limites inférieures exponentielles sur la taille des circuits. Cela a été prouvé par Pudlak: bornes inférieures pour la résolution et les épreuves de plans de coupe et les calculs monotones , J. of Symb. Logic 62 (3), 1997, pages 981 à 998.
Iddo Tzameret le
2
Grigory: Merci. J'ai débattu de l'opportunité de le mentionner dans le PO! Vous avez raison de dire que nous n'avons pas de limite inférieure superlinéaire explicite sur le nombre de portes XOR nécessaires pour calculer une fonction linéaire f: {0,1} <sup> n </ sup> & rarr; {0,1} < sup> n </ sup>. D’autre part, il n’est pas difficile de trouver des candidats pour les transformations linéaires qui <i> devraient </ i> nécessiter des portes & Omega; (n log n) XOR (la transformée de Fourier, la matrice "Joint de Sierpinski" ...) et Bram Cohen a proposé un exemple de fonction qui devrait nécessiter des portes XOR & Omega (n <sup> 3/2 </ sup>) (je ne m'en souviens pas, mais je pourrais le lui demander).
Scott Aaronson le
Même pour l'alphabet de taille 3, le réseau de clones est indénombrable et contient chaque réseau fini comme un sous-réseau. Il existe donc une infinité de bases d’opérations potentiellement intéressantes à prendre en compte. Je ne suis au courant d'aucun travail sur l'utilisation de clones non booléens pour les limites inférieures de circuits, mais cela semble intéressant d'explorer plus en profondeur.
András Salamon
3
Scott, connaissez-vous un analogue approprié pour la classe AC ^ 0 par rapport aux grands aphabets? Permettez-moi également de noter que l’on peut envisager les notions de monotonie pour les grands alphabets (Elchanan Mossel et moi-même avons parlé de seuils précis pour ceux qui se trouvaient devant front . monotonicité.
Gil Kalai

Réponses:

25

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

Image de réseau du message de Wikipedia

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 )

k3Lk20

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.

András Salamon
la source
Merci beaucoup, András! Je vais vérifier le papier de Ágoston et al. quand j'ai une chance. Entre-temps, j'ai parcouru la liste des clones les plus complets et les plus complets sur un ensemble de 3 éléments de Pantović et al. papier que vous avez lié, et je ne pense pas qu'aucun d'entre eux soit candidat à la "nouvelle" limite inférieure du circuit. (Pour certaines d'entre elles, les limites inférieures exponentielles découlent immédiatement de la limite inférieure monotone monotone de Razborov; pour d'autres, nous aurions besoin de limites inférieures pour les circuits généraux ou pour les circuits linéaires.) Mais même dans le cas k = 3, des clones plus petits que les pré-complétés semble toujours intéressant de regarder.
Scott Aaronson
15

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

f:0,1n0,1nΩ(n2log(n))

n2log(n)cc

Ω(nlogn)Ω(n3/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.

Grigory Yaroslavtsev
la source
11
  1. {0,1}aZ3n={0,1,2}nmin(x,y)xymod2f(a)=0a02est 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. a12n/nf

  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.2y=AxGF(2)nlog3/2nn1+cc>02

Stasys
la source
2
Chers Stasys, puis-je vous suggérer d’ enregistrer votre compte? Cela vous permettra d'utiliser le même compte d'utilisateur pour poster des réponses et de les éditer ultérieurement, entre autres. (Faites-moi savoir si vous décidez de vous inscrire et je vais fusionner vos comptes précédents avec elle afin que vous puissiez également modifier vos messages précédents.)
Kaveh
1
Merci, Kaveh, je me suis inscrit maintenant. La suggestion de Scott (accéder à des domaines plus vastes) peut également être intéressante d'un point de vue "pragmatique". Dites, quel est le plus petit nombre de portes max / plus dans un circuit pour le problème de sous-ensemble-somme avec la capacité du sac à dos ? Pour simuler l'algorithme de programmation dynamique standard, il suffit également d'autoriser les fils à effectuer des tests pour des entiers dans notre domaine. Cet algorithme donne également une borne supérieure sur le nombre de portes. Problème: prouver que les portes sont nécessaires. Cela signifierait que DP ne peut pas faire mieux pour Knapsack. Kxi=aanKΩ(nK)
Stasys