Was ist die Mindestgröße einer Schaltung, die die PARITÄT berechnet?

21

Es ist ein klassisches Ergebnis, dass jede Fan-In-2-UND-ODER-NICHT-Schaltung, die PARITÄT aus den Eingangsvariablen berechnet, eine Größe von mindestens und diese scharf ist. (Wir definieren Größe als die Anzahl der UND- und ODER-Gatter.) Der Beweis erfolgt durch Gattereliminierung und es scheint zu scheitern, wenn wir willkürliches Fan-In zulassen. Was ist für diesen Fall bekannt?3(n-1)

Kennt jemand ein Beispiel, bei dem ein größerer Fan-In hilft, dh wir brauchen weniger als Tore?3(n-1)

Update 18. Oktober. Marzio hat gezeigt, dass für sogar 5 Gatter mit der CNF-Form von PARITY ausreichen. Dies impliziert eine Schranke von 5n=35für allgemeinesn. Können SIE es besser machen?52n2n

domotorp
quelle
Dieses Papier kann verwandt sein. Die Basis ist hier jedoch viel größer als AND, OR.
Stasys
Die folgende Antwort bezieht sich (remote) auf Ihre Frage. cstheory.stackexchange.com/questions/3624/…
Hermann Gruber
1
In den und 53noberen Schranken ignorieren Sie Negationen eigentlichüberallund nicht nur bei Variablen, oder? 52n
Emil Jeřábek unterstützt Monica
1
Wie machen Sie das, ohne das Gate zu duplizieren, falls es sowohl positiv als auch negativ verwendet wird?
Emil Jeřábek unterstützt Monica
1
@Harry: Sie müssen k-1 Fan-in - Tore, aber sie können in der Tiefe platziert werden . Bei dieser Frage geht es um GRÖSSE und nicht um TIEFE! logk
Domotorp

Antworten:

10

Es ist möglich, die Parität mit nur 2,33n + C Gattern zu berechnen. Der Aufbau ist recht einfach und wird in diesem Artikel angegeben.

http://link.springer.com/article/10.3103/S0027132215050083

Hier ist ein Beispiel einer Schaltung für die Parität von 6 Variablen unter Verwendung von nur 12 Gattern (jedes Gate ist ein UND-Gatter, ein Kreis nahe dem Eingang eines Gatters bedeutet, dass dieser Eingang invertiert ist). Beachten Sie, dass eine Schaltung für die Parität von 6 Variablen, die durch Stapeln von DNF-Blöcken (wie in Marzios Obergrenze) aufgebaut ist, aus 13 Gattern besteht.

Ich habe überprüft, dass für n = 2,3,4,5,6 optimale Schaltkreisgrößen 3,5,8,10,12 sind. Diese Werte sind auch Schaltkreisgrößen, die eine Obergrenze von 2,33n ergeben. Ich weiß immer noch nicht, ob 2,33n die Größe der optimalen Schaltung für jedes n ist. Außerdem kenne ich die Größe der optimalen Schaltung für die Parität von 7 Variablen nicht (es gibt zwei mögliche Werte, 14 und 15). Schaltung für die Geduld von 6 Variablen

Yuri Kombarov
quelle
10

Diese untere Grenze für die Gate-Elimination stimmt nicht mit der oberen Grenze von Marzio überein, aber es ist ein Anfang.

Proposition: Jede unbegrenzte Fan-In-UND / ODER / NICHT-Paritätsberechnung für Variablen enthält mindestens 2 n - 1 UND- und ODER-Gatter.n22n1

Der Einfachheit halber verwende ich ein Modell, bei dem die einzigen Gatter UND-Gatter sind, wir jedoch Negationsdrähte zulassen. Es ist leicht zu erkennen, dass für n = 2 Gatter erforderlich sind , daher ist es ausreichend zu zeigen, dass wir , wenn C eine Schaltungsparität mit minimaler Größe für n > 2 Variablen ist, eine Einschränkung für eine Variable finden können, die mindestens tötet zwei Tore.3n=2Cn>2

Wenn eine Variable mindestens zwei positive Eltern hat (dh über nicht verbundene Drähte mit zwei verschiedenen Gattern verbunden ist), setzen Sie diese Variable auf 0xich0 werden die Eltern getötet, wird, und wir sind fertig; Ebenso, wenn es zwei negative Eltern hat. Wir können daher annehmen, dass jede Variable höchstens ein positives und höchstens ein negatives Elternteil hat.

Sei ein unteres Tor in der Schaltung. Ohne Beschränkung der Allgemeinheit, a = x 1x 2 . Setze x 1 = 0 , was a = 0 zwingt und tötet. Die eingeschränkte Schaltung C ' berechnet noch Parität, insbesondere es hängt von x 2 , also x 2 hat eine negative Mutter b = ¬ x 2c 1c r . Beachten Sie, dass ineinein=x1x2x1=0a=0Cx2x2b=¬x2c1cr , nein c j hängt von x 2 ab . Wenn es eine Zuweisung zu x 3 , , x n gäbe , die (über x 1 = 0 ) c j falsch macht, wäre die durch diese Zuweisung eingeschränkte Schaltung konstant, was der Tatsache widerspricht, dass sie x 2 oder ¬ x berechnet 2 . So wird in C ' ,alle die C j compute Konstante 1 und b berechnet ¬ xCcjx2x3,,xnx1=0cjx2¬x2Ccj1b , daher können wir es zusammen mit a beseitigen.¬x2a

EDIT: Wie ich aus Yuri Kombarovs Artikel erfahren habe, ist diese Untergrenze ebenso wie die 52n1obere Schranke impliziert durch die Antwort von Marzio De Biasi, wurden ursprünglich in bewiesen52n2

[1] Ingo Wegener, Die Komplexität der Paritätsfunktion in unbegrenzten Fan-In-Schaltkreisen mit unbegrenzter Tiefe , Theoretical Computer Science 85 (1991), No. 1, S. 155–170. http://dx.doi.org/10.1016/0304-3975(91)90052-4

Emil Jeřábek unterstützt Monica
quelle
Ja, die Frage ist also, ob wir 5 Gatter eliminieren können, indem wir 2 Variablen festlegen.
Domotorp
n
8

Ich erweitere meinen Kommentar:

kk1Ii2gi

|C|+i(Ii2)3(n1)

2) Wenn Sie einen beliebigen Fan zulassen , können Sie die -Grenze schlagen . Betrachten Sie beispielsweise die PARITÄT für 3 Variablen ( x 1 , x 2 , x 3 ) . Die folgende Schaltung berechnet es mit nur 5 beliebigen Fan-In-Gattern:3(n1)(x1,x2,x3)

Bildbeschreibung hier eingeben

Marzio De Biasi
quelle
Schön, in der Tat hat der CNF für n = 3 nur 5 Tore! Ich frage mich, ob man es überhaupt noch besser machen kann.
Domotorp
Ich habe nicht zu viel darüber nachgedacht, aber Sie können die obige Schaltung sicher kombinieren und parallel verwenden, um beispielsweise eine PARITY-Schaltung für 9 Variablen zu erhalten, die nur 20 Gates anstelle von 24 verwendet
Marzio De Biasi,
Ich habe und ich habe meine Frage aktualisiert.
Domotorp
2

Dies ist ein erweiterter Kommentar, der zeigt, was Emil argumentiert, wenn wir versuchen, die beweisen5n/2 Grenze zu . Hier können wir versuchen, 3 Gates mit einer Variablen oder 5 Gates mit zwei Variablen zu eliminieren.

Wenn es ein Literal mit 3 Eltern gibt, können wir alle 3 mit einer Variablen eliminieren.

Wenn zwei Literale zusammen in zwei verschiedenen Gates vorkommen, können wir das Hauptargument aus Emil's Antwort anwenden und wiederum drei Gates mit einer Variablen eliminieren.

domotorp
quelle