Conséquences pratiques de la

Contexte

La complexité du circuit est définie comme l'ensemble des familles de circuits (c'est-à-dire des séquences de circuits, une pour chaque taille d'entrée) de profondeur bornée et de taille polynomiale construites à l'aide de fan-in illimités ET, OU et NON. $AC^0$

La fonction de parité avec une entrée à bits est égale au XOR des bits en entrée. $\oplus$ $n$

L'un des premiers circuits à niveau inférieur éprouvé dans la complexité des circuits est le suivant:

[FSS81], [Ajt83]: . $\oplus \notin AC^0$

Des questions:

Soit la classe de fonctions qui peut être calculée à l'aide de circuits électroniques de profondeur bornée et de taille polynomiale à l'aide de composants électroniques comme des transistors. (J'ai inventé le nom , faites-moi savoir si vous connaissez un meilleur nom pour cela). $EC^0$ $EC^0$

Peut-on calculer en pratique en utilisant des circuits ? $\oplus$ $EC^0$

Qu'en est-il du fan-in illimité ET / OU? Pouvons-nous les calculer dans ? $EC^0$

Est ont des conséquences pratiques? L' important dans la pratique? $\oplus \notin AC^0$ $AC^0$

Pourquoi important pour les informaticiens (théoriques)? $\oplus \notin AC^0$

Remarque:

Ce message contient des questions intéressantes, mais OP semble refuser de le rendre plus lisible et d'y corriger les idées fausses pour une raison quelconque, donc j'en republie des questions. (Il serait plus facile de modifier le message d'origine mais actuellement il n'y a pas d'accord s'il est correct de modifier fortement le message d'un autre utilisateur.)

En relation:

Parité et $AC^0$
Pourquoi la parité n'est-elle pas importante dans ? $AC^0$ (Blog sur la complexité informatique)

cc.complexity-theory circuit-complexity physics bounded-depth Kaveh
la source

N C^{0}

$NC^{0}$ est la famille des circuits BOOLEAN comme mais de fan-in borné. Je ne sais pas grand-chose sur la complexité des circuits, donc je ne peux pas dire si l'électronique est booléenne. Cependant, je sais de l'architecture informatique que toutes les portes peuvent être implémentées à l'aide de transistors. Puisque vous avez un fanin borné, je suppose que vous avez également un nombre borné de transistors, donc vous ne violez pas la profondeur bornée et la taille du polynôme.

A C^{0}

$AC^{0}$

chazisop

@chazisop: Toutes les fonctions booléennes peuvent être implémentées en utilisant AND / OR / NOT, le fait est que l'implémentation est de la forme requise, c'est-à-dire polynomialement de nombreuses parties et profondeur limitée. Notez que peut également être défini en utilisant des portes fan-in 2 AND / OR, mais le nombre d'alternances de portes dans le circuit doit être limité. (Je pourrais avoir besoin de définir plus attentivement ce que nous entendons par profondeur pour un circuit électronique s'il n'est pas déjà défini dans la littérature.)

A C^{0}

$AC^0$

Kaveh

D'après ce dont je me souviens de mon cours d'architecture de premier cycle (lire: pas beaucoup), les circuits réels de votre ordinateur ne sont pas acycliques - ils ont des boucles de rétroaction et un état, et sont peut-être mieux modélisés comme des automates finis. Il me semble que s'il y a un décalage entre les résultats concernant et les résultats qui peuvent être appliqués à votre ordinateur portable, c'est la distinction clé, plutôt que d'utiliser des transistors pour implémenter vos portes ET.

A C^{0}

$AC^0$

Aaron Roth

@Aaron: Je ne me souviens pas non plus de grand-chose, mais je pense que les boucles étaient principalement destinées aux éléments de mémoire comme les tongs et les systèmes séquentiels. Je ne pense pas qu'il soit difficile de relier la complexité des circuits aux circuits logiques / numériques , en particulier aux systèmes combinatoires, la question est de savoir comment relier des concepts tels que la profondeur et le fan-in à des circuits électroniques fabriqués à partir de transistors. Je devrais peut-être le demander sur Physics.SE.

Kaveh

@Tsuyoshi Ito: Merci. Je viens de le vérifier sur Wikipedia, il semble que l'on puisse facilement implémenter des portes ET et OU illimitées en utilisant un nombre linéaire de NMOS . La structure des circuits est simple et ne change pas avec le nombre d'entrées de la porte. En revanche, le circuit XOR fabriqué à partir de transistors NMOS semble plus compliqué, je ne sais pas si il évolue bien avec l'augmentation du fan-in.

Kaveh

Réponses:

Je ne suis pas ingénieur électricien, mais je recherche des brevets en ligne concernant les circuits de commutation pour les portes de parité, et toutes les propositions (je n'ai trouvé de brevets que jusqu'à la fin des années 1970) discutent du problème de la taille par rapport à la profondeur. Les trois brevets que j'ai examinés proposent des solutions de profondeur logarithmique, basées sur des portes fanin-2. La réponse à votre première question est donc peut-être «non».

JJ Moyer: Parity Check Switching Circuit, brevet américain US3011073, 1961

AF Bulver et al.: Réalisation NAND Gate de la fonction de parité à n entrées, brevet américain US3718904, 1973

PJ Baun, Jr .: Parity Circuits, brevet américain US4251884, 1981

Hermann Gruber
la source

Très intéressant en effet.

Antonio E. Porreca

Johne, quel est ton problème? Vous essayez de discuter de choses que personne n'a jamais revendiquées. Personne n'a dit que la borne inférieure de parité pose une limite fondamentale au calcul de XOR avec des circuits autres que ceux auxquels le théorème s'applique (c'est-à-dire les circuits AC ^ 0). Il n'y a pas d'hypothèses cachées ou d'implications voilées ici. En particulier, nous savons tous par exemple qu'il est possible de calculer XOR avec des circuits NAND de taille polynomiale de profondeur logarithmique, même avec un fan-in constant.

La citation de Shannon est également largement hors de propos. Rien n'indique qu'il soupçonne même que les circuits ET-OU à profondeur constante doivent avoir une taille exponentielle pour calculer la parité. Bien sûr, il aurait pu deviner, car il est facile de conjecturer que cela devrait être vrai après avoir joué avec le problème pendant un certain temps, mais alors quoi?

Vous manquez complètement le point: prouver les limites inférieures est extrêmement difficile, et nous devons commencer quelque part, avec les modèles les plus simples. C'était essentiellement le premier circuit inférieur, les techniques conduisent à de nombreuses idées intéressantes (y compris dans d'autres domaines tels que la théorie de l'apprentissage), et bien que le résultat soit plausible, la preuve est perspicace et pas du tout triviale.

Le fait que le résultat semble intuitif ne le rend pas évident; si vous pensez que c'est le cas, veuillez fournir une preuve que la parité n'est pas dans AC ^ 0. Tout le monde sait que P n'est pas égal à NP trop d'ailleurs, mais personne n'est loin d'avoir une preuve.

Vos plaintes dans d'autres discussions sur les portes NAND n'ont aucun sens non plus. Cette limite inférieure est également valable pour les circuits à profondeur constante construits à partir de portes NAND, car ils sont fondamentalement les mêmes. Choisir d'énoncer le résultat avec AND, OR, NOT n'est qu'une question de commodité. Donc, cela peut être une application du monde réel dans les termes que vous aimez: les circuits à profondeur constante des portes NAND calculant la parité nécessitent une taille exponentielle. Cela donne une limitation pratique, même si ce n'est pas la chose la plus importante. Il indique que les petits circuits XOR pour un grand nombre n d'entrées doivent avoir une profondeur croissante avec n ou des portes autres que NAND. Pourquoi n'êtes-vous pas satisfait de cela?

Votre affirmation selon laquelle la profondeur du circuit n'est pas un problème dans le monde réel est également très trompeuse, car la profondeur est directement liée au temps et à la fréquence maximale à laquelle l'horloge peut fonctionner.

Soit dit en passant, la communauté CS était bien au courant de la théorie du circuit booléen EE et s'est appuyée sur cela, contrairement à ce que vous prétendez.

David
la source

merci pour la réponse, mais une grande partie de votre réponse est des commentaires adressés à johne et non à mes questions. Je comprends que vous avez probablement posté cela comme une réponse parce que vous ne pouvez pas commenter , mais je ne veux pas ce tour de la question dans une discussion entre vous deux, donc pourriez - vous s'il vous plaît déplacer la partie de votre réponse qui est dirigée vers lui à la question connexe posté par lui? (ou à la méta discussion ) Merci d'avance.

Kaveh

Le lien suivant donne un aperçu de la plupart des portes CMOS. Notez que "ET OU inversé" (AOI) et "OU ET inversé" (OAI) dans le lien. Ces circuits représentent généralement une fraction de la taille qu'il faudrait pour créer le même circuit en utilisant leurs composants discrets. Par exemple, un circuit OAI33 (tiré d'une bibliothèque de cellules standard de fonderies commerciales) prend environ , mais la construction du même circuit en utilisant les cellules discrètes équivalentes prend environ . $1.62^2$ $3.82^2$

Structures des circuits logiques de la technologie CMOS

Ce qui suit décrit un circuit d'additionneur complet à huit transistors, qui est généralement défini en algèbre booléenne comme . A titre de comparaison, une porte typique {NAND, OR, XOR, etc} à 2 entrées est généralement composée de quatre à huit transistors. $s = a \oplus b \oplus c_{in}$

Cellule d'addition complète 8T haute vitesse et faible puissance

Un bon endroit pour trouver des portes XOR / XNOR compactes à haute vitesse est dans les additionneurs complets et les circuits ECC de Hamming (qui sont généralement dans le chemin critique).

En outre, le problème de la profondeur du circuit n'est généralement pas un problème dans la logique synchrone VLSI. La seule profondeur de toute conséquence est le chemin critique, qui définit la période d'horloge maximale. La grande majorité de la logique combinatoire propage ses résultats en une fraction du temps pour le chemin critique. Les chemins critiques ont tendance à se produire avec une logique combinatoire qui doit traverser plusieurs zones dispersées sur une puce.

Plusieurs fois, il est possible de "canaliser" la logique combinatoire pour répondre aux contraintes de synchronisation. Cela a pour effet de créer un circuit qui prend une nouvelle entrée et produit une nouvelle sortie à chaque cycle d'horloge, mais a une latence de cycles d'horloge avant qu'une entrée donnée ne soit disponible sur la sortie. Cela a tendance à rendre la plupart des circuits ~ en pratique. $n$ $O(1)$

Vous pouvez trouver le document d'intérêt suivant, qui traite de la complexité VLSI : $AT^2 = \Omega(n^2)$

Sur la complexité des implémentations VLSI et des représentations graphiques de fonctions booléennes avec application à la multiplication d'entiers

C'est du blog de complexité de calcul:

Cela soulève la question: est-ce que certaines personnes dans le monde réel veulent vraiment construire des circuits fanin ET-OU-NON polysize à profondeur constante pour PARITY, et ce résultat leur dit-il pourquoi ils ne peuvent pas?

À quoi la réponse est: non , personne ne construit de cette façon des circuits PARITY dans le monde réel. La dernière fois que quelqu'un a voulu le faire, c'est lorsque la seule chose avec laquelle ils ont dû travailler était des relais mécaniques et c'est pourquoi le résultat Shannons ~ borne inférieure pour la plupart des circuits est pour {AND, OR, NOT}. Même Shannon savait que XOR ne pouvait pas être représenté efficacement en utilisant simplement {AND, OR, NOT}: $2^n/n$

Il peut être démontré par une étude de cas particuliers que , la fonction $\lambda(3) = 8$

$X \oplus Y \oplus Z = X(YZ+Y'Z') + X'(YZ'+Y'Z)$

nécessitant huit éléments dans sa réalisation la plus économique. , cependant, est en fait 3. Il semble probable que, en général, la fonction $\mu(3)$

$X_1 \oplus X_2 \oplus \ldots \oplus X_n$

nécessite éléments mais aucune preuve n'a été trouvée. $4(n-1)$

johne
la source

Tahnks johne pour la réponse, mais pour le moment je manque un peu de temps mais je vais lire votre réponse plus attentivement et regarder les articles auxquels vous avez lié quand je trouverai du temps libre. J'ai également parlé avec des amis du département EE et j'ai appris quelques choses intéressantes que je publierai.

Kaveh