Praktische Konsequenzen von

10

Hintergrund

Die Schaltungskomplexität ist definiert als der Satz von Schaltungsfamilien (dh Folgen von Schaltungen, eine für jede Eingangsgröße) mit begrenzter Tiefe und Polynomgröße, die unter Verwendung von unbegrenztem Fan-In AND, OR und NOT erstellt wurden.AC0

Die Paritätsfunktion mit Bit-Eingabe ist gleich dem XOR der Bits in der Eingabe.n

Eine der ersten Schaltungsuntergrenzen, die sich in der Schaltungskomplexität bewährt haben, ist die folgende:

[FSS81], [Ajt83]: .AC0


Fragen:

Sei die Klasse von Funktionen, die unter Verwendung elektronischer Schaltungen mit begrenzter Tiefe und Polynomgröße unter Verwendung elektronischer Teile wie Transistoren berechnet werden können . (Ich habe mir den Namen ausgedacht, lass es mich wissen, wenn du einen besseren Namen dafür kennst).EC0EC0

  1. Können wir in der Praxis mit Schaltkreisen berechnen ?EC0

  2. Was ist mit unbegrenztem Fan-In UND / ODER? Können wir sie in berechnen ?EC0

  3. Hat praktische Konsequenzen? Ist in der Praxis wichtig?AC0AC0

  4. Warum ist für (theoretische) Informatiker wichtig?AC0


Hinweis:

Dieser Beitrag enthält interessante Fragen, aber OP scheint sich aus irgendeinem Grund zu weigern, den Beitrag lesbarer zu machen und das Missverständnis darin zu beheben. Deshalb reposte ich Fragen daraus. (Es wäre einfacher, den ursprünglichen Beitrag zu bearbeiten, aber derzeit gibt es keine Vereinbarung, ob es in Ordnung ist, den Beitrag eines anderen Benutzers stark zu bearbeiten.)

Verbunden:

Kaveh
quelle
NC0 ist die Familie der BOOLEAN-Schaltkreise wie jedoch mit begrenztem Fan-In. Ich weiß nicht viel über die Komplexität von Schaltkreisen, daher kann ich nicht sagen, ob elektronisch gleich boolesch ist. Aus der Computerarchitektur weiß ich jedoch, dass alle Gates mit Transistoren implementiert werden können. Da Sie ein begrenztes Fanin haben, haben Sie vermutlich auch eine begrenzte Anzahl von Transistoren, sodass Sie die begrenzte Tiefe und Polynomgröße nicht verletzen. AC0
Chazisop
@chazisop: Alle Booleschen Funktionen können mit AND / OR / NOT implementiert werden. Der Punkt ist, ob die Implementierung die erforderliche Form hat, dh polynomiell viele Teile und begrenzte Tiefe. Es ist zu beachten, dass alternativ unter Verwendung von Fan-In-2-UND / ODER-Gattern definiert werden kann, aber die Anzahl der Wechsel von Gattern in der Schaltung sollte begrenzt sein. (Ich muss möglicherweise genauer definieren, was wir unter Tiefe für eine elektronische Schaltung verstehen, wenn dies nicht bereits in der Literatur definiert ist.)AC0
Kaveh
Soweit ich mich an meinen Architekturstudiengang erinnere (lesen Sie: nicht viel), sind die tatsächlichen Schaltkreise in Ihrem Computer nicht azyklisch - sie haben Rückkopplungsschleifen und -zustände und sind möglicherweise besser als endliche Automaten modelliert. Es scheint mir, dass wenn es eine Trennung zwischen den Ergebnissen zu und den Ergebnissen gibt, die auf Ihren Laptop angewendet werden können, dies die Hauptunterscheidung ist, anstatt Transistoren zur Implementierung Ihrer UND-Gatter zu verwenden. AC0
Aaron Roth
@ Aaron: Ich erinnere mich auch nicht an viel, aber ich denke, Schleifen waren hauptsächlich für Speicherelemente wie Flipflops und sequentielle Systeme gedacht. Ich denke nicht, dass es schwierig ist, die Schaltungskomplexität mit logischen / digitalen Schaltungen, insbesondere den kombinatorischen Systemen, in Beziehung zu setzen. Die Frage ist, wie Konzepte wie Tiefe und Fan-In mit elektronischen Schaltungen aus Transistoren in Beziehung gesetzt werden können. Vielleicht sollte ich es auf Physics.SE fragen.
Kaveh
3
@ Tsuyoshi Ito: Danke. Ich habe es gerade auf Wikipedia überprüft, es scheint, dass man leicht unbegrenzte UND- und ODER- Gatter unter Verwendung der linearen Anzahl von NMOS implementieren kann . Die Struktur der Schaltungen ist einfach und ändert sich nicht mit der Anzahl der Eingänge in das Gate. Andererseits scheint eine XOR- Schaltung aus NMOS-Transistoren komplizierter zu sein. Ich weiß nicht, ob sie mit zunehmendem Fan-In gut skaliert.
Kaveh

Antworten:

10

Ich bin kein Elektrotechniker, sondern suche nach Online-Patenten für Schaltkreise für Paritätsgatter. In allen Vorschlägen (ich habe Patente nur bis Ende der 1970er Jahre gefunden) wird das Problem der Größe gegenüber der Tiefe erörtert. Alle drei Patente, die ich mir angesehen habe, schlagen Lösungen mit logarithmischer Tiefe vor, die auf Fanin-2-Gates basieren. Die Antwort auf Ihre erste Frage lautet also möglicherweise "Nein".

JJ Moyer: Parity Check Switching Circuit, US-Patent US3011073, 1961

AF Bulver et al.: NAND-Gate-Realisierung der Paritätsfunktion mit n Eingängen, US-Patent US3718904, 1973

PJ Baun, Jr.: Parity Circuits, US-Patent US4251884, 1981

Hermann Gruber
quelle
Sehr interessant.
Antonio E. Porreca
6

Johne, was ist dein Problem? Sie versuchen, über Dinge zu streiten, die niemand jemals behauptet hat. Niemand sagte, dass die untere Paritätsgrenze eine grundlegende Grenze für die Berechnung von XOR mit anderen Schaltungen als denen darstellt, für die der Satz gilt (dh AC ^ 0-Schaltungen). Hier gibt es keine versteckten Annahmen oder verschleierten Implikationen. Insbesondere wissen wir alle zum Beispiel, dass es möglich ist, XOR mit polynomgroßen NAND-Schaltungen mit logarithmischer Tiefe zu berechnen, selbst bei konstantem Fan-In.

Shannons Zitat ist ebenfalls weitgehend irrelevant. Es gibt dort keinen Hinweis darauf, dass er sogar vermutet hat, dass UND-ODER-Schaltungen mit konstanter Tiefe eine exponentielle Größe haben müssen, um die Parität zu berechnen. Natürlich hätte er es erraten können, da es leicht zu vermuten ist, dass dies wahr sein sollte, nachdem er eine Weile mit dem Problem gespielt hat, aber was nun?

Sie verpassen völlig den Punkt: Es ist äußerst schwierig, die unteren Grenzen zu beweisen, und wir müssen irgendwo mit den einfachsten Modellen beginnen. Dies war im Wesentlichen die Untergrenze der ersten Schaltung, die Techniken führten zu vielen interessanten Ideen (einschließlich anderer Bereiche wie der Lerntheorie), und obwohl das Ergebnis plausibel ist, ist der Beweis aufschlussreich und überhaupt nicht trivial.

Die Tatsache, dass das Ergebnis intuitiv erscheint, macht es nicht offensichtlich; Wenn Sie glauben, dass dies der Fall ist, legen Sie bitte einen Beweis dafür vor, dass die Parität nicht in AC ^ 0 enthalten ist. Jeder weiß, dass P auch in dieser Hinsicht nicht gleich NP ist, aber niemand hat annähernd einen Beweis.

Ihre Beschwerden in anderen Threads über NAND-Gates machen ebenfalls keinen Sinn. Diese Untergrenze gilt ebenso gut für Schaltungen mit konstanter Tiefe, die aus NAND-Gattern aufgebaut sind, da sie im Grunde gleich sind. Die Entscheidung, das Ergebnis mit AND, OR, NOT anzugeben, ist nur eine Frage der Bequemlichkeit. Dies kann also eine reale Anwendung sein, wie Sie es möchten: Schaltungen mit konstanter Tiefe von NAND-Gattern, die die Parität berechnen, erfordern eine exponentielle Größe. Es gibt eine praktische Einschränkung, auch wenn dies nicht das Wichtigste ist. Es heißt, dass kleine XOR-Schaltungen für eine große Anzahl von n Eingängen entweder eine mit n wachsende Tiefe oder andere Gatter als NAND aufweisen müssen. Warum bist du damit nicht zufrieden?

Ihre Behauptung, dass die Schaltungstiefe in der realen Welt kein Problem darstellt, ist ebenfalls sehr irreführend, da die Tiefe in direktem Zusammenhang mit der Zeit und der maximalen Frequenz steht, mit der die Uhr arbeiten kann.

Übrigens war sich die CS-Community der EE-Booleschen Schaltungstheorie bewusst und baute darauf auf, entgegen Ihrer Behauptung.

David
quelle
2
danke für die antwort, aber ein großer teil deiner antwort sind kommentare an johne und nicht an meine fragen. Ich verstehe, dass Sie dies wahrscheinlich als Antwort gepostet haben, weil Sie keinen Kommentar abgeben können, aber ich möchte nicht, dass diese Frage zu einer Diskussion zwischen Ihnen beiden wird. Könnten Sie also bitte den Teil Ihrer Antwort, der an ihn gerichtet ist, auf die entsprechende Frage verschieben Gepostet von ihm? (oder zur Metadiskussion ) Vielen Dank im Voraus.
Kaveh
1

Der folgende Link gibt einen Überblick über die meisten CMOS-Gatter. Beachten Sie, dass "AND OR Inverted" (AOI) und "OR AND Inverted" (OAI) im Link enthalten sind. Diese Schaltungen sind typischerweise ein Bruchteil der Größe, die erforderlich wäre, um dieselbe Schaltung unter Verwendung ihrer diskreten Komponenten zu erzeugen. Zum Beispiel nimmt eine OAI33-Schaltung (entnommen aus einer Standardzellbibliothek einer kommerziellen Gießerei) eine Fläche von ~ ein, aber der Aufbau derselben Schaltung unter Verwendung der äquivalenten diskreten Zellen benötigt ~ Fläche.3,82 21.6223.822

Das Folgende beschreibt eine Volladdiererschaltung mit acht Transistoren, die typischerweise in der Booleschen Algebra als . Zum Vergleich besteht ein typisches 2-Eingangs-Gate (NAND, OR, XOR usw.) typischerweise aus vier bis acht Transistoren.s=abcin

Ein guter Ort, um kompakte XOR / XNOR-Hochgeschwindigkeitsgatter zu finden, sind Volladdierer und Hamming-ECC-Schaltungen (die sich typischerweise im kritischen Pfad befinden).

Außerdem ist das Problem der Schaltungstiefe in der synchronen VLSI-Logik normalerweise kein Problem . Die einzige Tiefe einer Konsequenz ist der kritische Pfad, der die maximale Taktperiode definiert. Die überwiegende Mehrheit der kombinatorischen Logik verbreitet ihre Ergebnisse in einem Bruchteil der Zeit für den kritischen Pfad. Kritische Pfade treten in der Regel mit einer kombinatorischen Logik auf, die mehrere Bereiche durchlaufen muss, die über einen Chip verstreut sind.

Oft ist es möglich, kombinatorische Logik zu "pipettieren", um die zeitlichen Einschränkungen zu erfüllen. Dies hat den Effekt, dass eine Schaltung erzeugt wird, die einen neuen Eingang nimmt und bei jedem Taktzyklus einen neuen Ausgang erzeugt, jedoch eine Latenz von Taktzyklen aufweist, bevor ein bestimmter Eingang am Ausgang verfügbar ist. Dies führt in der Praxis dazu, dass die meisten Schaltungen ~ .O ( 1 )nO(1)

Möglicherweise finden Sie das folgende interessante Dokument, in dem die Komplexität von VLSI erläutert wird :AT2=Ω(n2)

Dies ist aus dem Computation Complexity Blog:

Dies wirft die Frage auf: Wollen einige Menschen in der realen realen Welt wirklich unbegrenzte Fanin-AND-OR-NOT-Schaltungen mit konstanter Tiefe für die PARITÄT konstruieren, und sagt ihnen dieses Ergebnis, warum sie dies nicht können?

Die Antwort lautet: Nein , niemand baut auf diese Weise PARITÄTS-Schaltkreise in der realen Welt. Das letzte Mal, dass jemand dies tun wollte, war, als das einzige, mit dem er arbeiten musste, mechanische Relais waren, und deshalb ist Shannons ~ Untergrenze für die meisten Schaltkreise das Ergebnis für {AND, OR, NOT}. Sogar Shannon wusste, dass XOR nicht effizient mit nur {AND, OR, NOT} dargestellt werden konnte:2n/n

Durch eine Untersuchung von Sonderfällen kann gezeigt werden, dass die Funktion istλ(3)=8

XYZ=X(YZ+YZ)+X(YZ+YZ)

erfordert acht Elemente in seiner wirtschaftlichsten Realisierung. ist jedoch tatsächlich 3. Es scheint wahrscheinlich, dass im Allgemeinen die Funktionμ(3)

X1X2Xn

erfordert Elemente, aber es wurde kein Beweis gefunden.4(n1)

Johne
quelle
Tahnks Johne für die Antwort, aber im Moment habe ich ein bisschen Zeit, aber ich werde Ihre Antwort genauer lesen und mir die Artikel ansehen, auf die Sie verlinkt haben, wenn ich etwas Freizeit finde. Ich habe auch mit einigen Freunden aus der EE-Abteilung gesprochen und ein paar interessante Dinge gelernt, die ich veröffentlichen werde.
Kaveh