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

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. $n$ $2n-2$

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. " $f_n(x) = x_1\dots x_n \lor \bar{x}_1 \dots \bar{x}_n$ $n+\Omega(1)$

cc.complexity-theory lower-bounds circuit-complexity Alexander S. Kulikov
quelle

@ 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

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

2 n - 2

$2n-2$

Ryan Williams

@Sasha, haben Sie versucht, SAT-Löser auf kleine Beispiele anzuwenden (wie ), wie in einigen Ihrer früheren Artikel?

n = 4

$n=4$

Ryan Williams

@ 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).

C_{3} = 3

$C_3=3$

C_{4} = 5

$C_4=5$

C_{5} \leq 7

$C_5 \le 7$

1

$1$

n

$n$

2 n - 3

$2n-3$

2 n - 3

$2n-3$

x_{i} \equiv x_{i + 1}

$x_i \equiv x_{i+1}$

i = 1, \dots, n - 1

$i=1,\dots,n-1$

(n - 1)

$(n-1)$

(n - 2)

$(n-2)$

Alexander S. Kulikov

@ Tsuyoshi: Ich denke, dass die Gate Funktion von Sasha die zweite Funktion der Frage ist ( ), die es kann mit XNOR-Gattern (angewendet auf ) und

2 n - 3

$2n-3$

f_{n} (x) = x_{1} \dots x_{n} \lor {\bar{x}}_{1} \dots {\bar{x}}_{n}

$f_n(x) = x_1\dots x_n \lor \bar{x}_1 \dots \bar{x}_n$

n - 1

$n-1$

x_{i}, x_{i + 1}

$x_i,x_{i+1}$

uNDGatter auf die XNORs angewandt.

n - 2

$n-2$

Marzio De Biasi

Antworten:

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 gebunden senken Methoden von Blum & Seysen erhalten werden kann , verwendet wird , aber es scheint dies nicht der Fall ist. $x_1\dots x_n\vee \bar{x}_1\dots\bar{x}_n$ $2n-c$

Vladimir Lysikov
quelle

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

@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

2 n - 2

$2n-2$

C (f_{n}) \geq C (A N D, O R) - c \geq 2 n - c^{'}

$C(f_n) \ge C(AND,OR)-c \ge 2n-c'$

Alexander S. Kulikov

2 n - 2

$2n-2$

x_{1} \dots x_{n} \lor {\bar{x}}_{1} \dots {\bar{x}}_{n}

$x_1\dots x_n\vee \bar{x}_1\dots \bar{x}_n$

2 n - 5

$2n-5$

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\lfloor n/2 \rfloor$

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.

$3\lfloor n/2 \rfloor$

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

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