Gewichtsannahme in Schwellwertschaltungen

8

Ein Schwellenwertgatter, das eine lineare Schwellenwertfunktion an booleschen Eingängen implementiert ist durch die Gleichung gegeben: wobei . Die werden als Gewichte der Schwellenwertfunktion bezeichnet, und wird als Schwellenwert bezeichnet, und natürlich das Gate einenx1,x2,xnw1x1+w2x2+,wnxntw1,,wn,tRwit1 an einem Eingang ausx wenn die durch die obige Gleichung angegebene gewichtete Summe überschreitet t.

Jetzt, fast überall in der Literatur zu Schwellenwertschaltungen, stoße ich auf diese Tatsache (die ich vermute, ist Folklore, da ich nirgendwo einen Beweis finden konnte): Die wi's in der obigen linearen Gleichung können ganze Zahlen gemacht werden (on nlognBits), und eine Schwellenwertschaltung, die aus diesen Gattern besteht, berechnet immer noch, was mit realen Gewichten möglich war. Ich habe darüber nachgedacht, und ich denke, es muss ein einfacher Trick sein, aber ich habe keinen Beweis für diese Tatsache erhalten. Kann mir jemand helfen oder eine Referenz geben? (Die einzige Referenz, die ich finden konnte, war ein Text von Muroga, den ich nicht beschaffen konnte.)

Nikhil
quelle

Antworten:

6

Gegeben w1,,wn,t, Lassen X die Menge der Aufgaben so sein, dass iwixitund betrachten Sie das lineare Programm mit Variablen z1,,zn und der 2n Einschränkungen

izixi+1(x1,,xn)Xizixi1(x1,,xn)X
Dieses lineare Programm (mit konstanter Zielfunktion) ist möglich (seit zi=wi/t ist eine Lösung) und hat auch eine Lösung z1,,znDas ist ein Scheitelpunkt. Als solches ist es die Lösung eines Systems vonn Gleichungen der Form
izixi=±1.
Cramers Regel gibt jeden zi als Verhältnis von zwei n×n Determinanten von Matrizen von 0,±1Einträge; in der Tat ist der Nenner der gleiche. Jeder ZählerNi und der gemeinsame Nenner D ist höchstens n! in der Größe, also multiplizieren Sie alles mit Derhalten wir eine integrale Lösung N1,,Nn,D, wo alle Mengen höchstens sind n!nn=2nlogn in der Größe.
Yuval Filmus
quelle
1
Es scheint mir, dass Sie mit diesem linearen Programm riskieren, dass die Scheitelpunktlösung nicht dieselbe Funktion wie die ursprüngliche hat: Die beiden Gleichungssätze haben dieselbe rechte Seite, und daher riskieren Sie, dass die lineare Form gegeben durch die Scheitelpunktlösung haben den gleichen Wert auf Eingaben beide von X und nicht von X. Um dies zu beheben, sollten die rechten Seiten unterschiedlich sein. Der normale Beweis, den ich kenne, verwendetn+1 Variablen (dh auch eine Variable für t) und verwendet die rechte Seite 1 und 1.
Kristoffer Arnsfelt Hansen
@Kristoffer Du hast recht, es war ein Tippfehler. ich meinte+1 und 1, wie du schreibst.
Yuval Filmus
@YuvalFilmus Gibt es einen Tippfehler beim Zählen der Anzahl der zu lösenden Gleichungen? Es scheint, als hättest du2nsimultane lineare Gleichungen zu lösen. (eine für jedenx) Und daher sind alle Lösungen höchstens (2n)! in der Größe, weil die Cramer-Regelmatrizen sind 2ndimensional. Vermisse ich etwas
Gradstudent
Oh! Warten! Wollen Sie damit sagen, dass man jeden wählen kann?n des xs willkürlich und das Lösen nach diesem Subsystem reicht aus, um Ihnen einen Scheitelpunkt zu geben, und damit sind Sie fertig?
Gradstudent
Ein Scheitelpunkt ist die Lösung von nlinear unabhängige Gleichungen.
Yuval Filmus