Anzahl der Binärgatter, die benötigt werden, um UND und ODER von n Eingangsbits gleichzeitig zu berechnen

16

Wie viele binäre Gatter sind mindestens erforderlich, um UND und ODER von Eingangsbits gleichzeitig zu berechnen ? Die triviale Obergrenze ist . Ich glaube, das ist optimal, aber wie kann man das beweisen? Die Standard-Gate-Eliminierungstechnik funktioniert hier nicht, da durch Zuweisen einer Konstanten zu einer der Eingangsvariablen einer der Ausgänge trivialisiert wird.n2n2

Das Problem wird auch als Übung 5.12 im Buch "Komplexität boolescher Funktionen" von Ingo Wegener in etwas anderer Form angegeben: "Sei . Mit der Eliminierungsmethode kann man nur eine untere Schranke der Größe beweisen. Versuchen Sie, größere untere Schranken zu beweisen. "fn(x)=x1xnx¯1x¯nn+Ω(1)

Alexander S. Kulikov
quelle
1
@ Ryan: Die Frage handelt nicht von UND von ODER, sondern von UND und ODER. Die Antwort auf Sashas Frage kenne ich allerdings nicht.
Tsuyoshi Ito
1
@ TsuyoshiIto Danke, irgendwie habe ich es geschafft, es falsch zu analysieren. Es ist definitiv ein nicht triviales Problem - man könnte sich vorstellen, andere Arten von Toren zu verwenden, um einen Vorteil gegenüber erzielen . 2n2
Ryan Williams
2
@Sasha, haben Sie versucht, SAT-Löser auf kleine Beispiele anzuwenden (wie ), wie in einigen Ihrer früheren Artikel? n=4
Ryan Williams
2
@ Ryan Ja, sicher. Was wir wissen ist, dass , , . Dies ist für die Funktion aus dem Buch (es ist wenn alle Eingabebits gleich sind). Dies wächst wie . Und eine Schaltung der Größe ist einfach zu konstruieren: Berechne zuerst für alle ( Gatter) und dann die Konjunktion von ihnen ( Tore). C3=3C4=5C571n2n32n3xixi+1i=1,,n1(n1)(n2)
Alexander S. Kulikov
1
@ Tsuyoshi: Ich denke, dass die Gate Funktion von Sasha die zweite Funktion der Frage ist ( ), die es kann mit XNOR-Gattern (angewendet auf ) und2n3fn(x)=x1xnx¯1x¯nn1xi,xi+1 uNDGatter auf die XNORs angewandt. n2
Marzio De Biasi

Antworten:

14

Dieses Papier von Blum & Seysen kann nützlich sein:

N. Blum, M. Seysen. Charakterisierung aller optimalen Netzwerke zur simultanen Berechnung von AND und NOR . Acta Inf. 21: 171-181 (1984)

Ich habe gedacht , dass für 2 n - c gebunden senken Methoden von Blum & Seysen erhalten werden kann , verwendet wird , aber es scheint dies nicht der Fall ist.x1xnx¯1x¯n 2nc

Vladimir Lysikov
quelle
1
Gibt es eine öffentliche PDF-Version des Blum- und Seysen-Papiers?
Marzio De Biasi
@Vladimir, danke für den Hinweis! Ich werde versuchen zu überprüfen, ob ihre Methoden in diesem Fall anwendbar sind, wenn ich den Artikel finde.
Alexander S. Kulikov
3
@Vladimir, dann schon wieder! Tatsächlich enthält diese Arbeit genau die Antwort auf meine Frage und noch mehr: Um UND und ODER gleichzeitig zu berechnen, braucht man und jede Schaltung dieser Größe berechnet UND und ODER unabhängig voneinander (das ist interessant!). Es ist auch nicht schwierig zu zeigen, dass C ( f n ) C ( A N D , O R ) - c 2 n - c 'ist . 2n2C(fn)C(AND,OR)c2nc
Alexander S. Kulikov
2n2x1xnx¯1x¯n2n5
1
Nur eine Erinnerung @SashaK. Wenn dir die Antwort gefällt, "akzeptiere" sie bitte, indem du auf das Häkchen unter der Stimmenzahl klickst.
Suresh Venkat
3

3n/2

Der clevere Algorithmus, der die obere Schranke beweist, übersetzt in eine UND / ODER-Schaltung mit derselben Schranke, die Sie erhalten, da einer der Vergleiche sowohl ein Minimum als auch ein Maximum berechnet.

3n/2

Die obere Grenze wird in "Einführung in Algorithmen" angezeigt, wo Sie auch das einfache Argument finden, das zeigt, dass Max / Min-Komparatorschaltungen gültig sind, wenn sie für boolesche Eingaben funktionieren (verwenden Sie einen geeigneten Schwellenwert). Die untere Schranke finden Sie zB hier .

Yuval Filmus
quelle
2
Beachten Sie in Sashas Frage, dass alle 2-Bit-Booleschen Funktionen zum Aufbau der Schaltung verwendet werden können.
Ryan Williams
Ja, es ist nicht klar, wie die Untergrenze für alle Binärfunktionen übersetzt werden kann.
Alexander S. Kulikov