Adlemans Theorem über unendliche Halbwertszeiten?

Adleman hat 1978 gezeigt, dass : Wenn eine boolesche Funktion von Variablen durch eine probabilistische boolesche Schaltung der Größe berechnet werden kann , dann kann auch durch eine deterministische berechnet werden Boolesche Schaltung des Größenpolynoms in und ; eigentlich von Größe . f n M f M n O ( n M $\mathrm{BPP}\subseteq \mathrm{P/poly}$$f$$n$$M$$f$$M$$n$$O(nM)$

Allgemeine Frage: Über welche anderen (als booleschen) Semirings verfügt ? $\mathrm{BPP}\subseteq \mathrm{P/poly}$

gesagt, eine probabilistische Schaltung über einem Semiring verwendet ihre Operationen "Addition" und "Multiplikation" als Gatter . die Eingänge sind Eingangsvariablen und möglicherweise eine Anzahl von zusätzlichen Zufallsvariablen, die die Werte nehmen und unabhängig voneinander mit einer Wahrscheinlichkeit , hier und sind jeweils die additiven und multiplikativen Identitäten des Halbrings Eine solche Schaltung berechnet eine gegebene Funktion ( S , + , ⋅ , 0 , 1 ) ( + ) ( ⋅ ) x 1 , ... , x n 0 1 1 / 2 0 1 $\mathsf{C}$$(S,+,\cdot,0,1)$$(+)$$(\cdot)$$x_1,\ldots,x_n$$0$$1$$1/2$$0$$1$$\mathsf{C}$ $f:S^n\to S$wenn für jedes , . $x\in S^n$$\mathrm{Pr}[\mathsf{C}(x)=f(x)]\geq 2/3$

Die Abstimmungsfunktion von Variablen ist eine Teilfunktion, deren Wert wenn das Element mehr als Mal unter und undefiniert ist , falls kein solches Element existiert. Eine einfache Anwendung von Chernoffs und Vereinigungsgrenzen ergibt das Folgende.$\mathrm{Maj}(y_1,\ldots,y_m)$$m$$y$$y$$m/2$$y_1,\ldots,y_m$$y$

Majoritäts-Trick: eine probabilistische Schaltung eine Funktion auf einer endlichen Menge , so gibt es Realisierungen von so dass für alle . $\mathsf{C}$$f:S^n\to S$$X\subseteq S^n$$m=O(\log|X|)$$C_1,\ldots,C_m$$\mathsf{C}$$f(x)=\mathrm{Maj}(C_1(x),\ldots,C_m(x))$$x\in X$

Während des Booleschen Semirens ist die Abstimmungsfunktion die Mehrheitsfunktion und hat kleine (sogar monotone) Schaltkreise. Also folgt Adlemans Theorem mit . $\mathrm{Maj}$$X=\{0,1\}^n$

Aber was ist mit anderen (besonders unendlichen) Semirings? Was ist mit dem arithmetischen Semiring (mit gewöhnlicher Addition und Multiplikation)?$(\mathbb{N},+,\cdot,0,1)$

Frage 1: Hält über das arithmetische Semiring? $\mathrm{BPP}\subseteq \mathrm{P/poly}$

Obwohl ich für "Ja" gewettet habe, kann ich dies nicht zeigen.

Bemerkung: Mir ist bekannt , dass die Autoren behaupten, über dem realen Feld . Sie beschäftigen sich mit nicht-monotonen arithmetischen Schaltungen und kommen (in Satz 4) auch zu Schaltungen mit der Abstimmungsfunktion als Ausgangsgatter. Aber wie kann man dieses -Tor durch eine arithmetische Schaltung simulieren (sei es monoton oder nicht)? Dh wie bekommt man ihr Korollar 3?$\mathrm{BPP}\subseteq \mathrm{P/poly}$$(\mathbb{R},+,\cdot,0,1)$$\mathrm{Maj}$$\mathrm{Maj}$

Tatsächlich scheint das folgende einfache Argument, das mir Sergey Gashkov (von der Moskauer Universität) vorgetragen hat, zu zeigen, dass dies unmöglich ist (zumindest für Schaltungen, die nur Polynome berechnen können ). Angenommen, wir können als Polynom ausdrücken . Dann impliziert , impliziert und impliziert . Dies gilt, weil über Felder mit der Charakteristik Null die Gleichheit der Polynomfunktionen die Gleichheit der Koeffizienten bedeutet. Beachten Sie, dass in Frage 1 der Bereich der probabilistischen Schaltkreise und damit der Bereich der$\mathrm{Maj}(x,y,z)$$f(x,y,z)=ax+by+cz+ h(x,y,z)$$f(x,x,z)=x$$c=0$$f(x,y,x)=x$$b=0$$f(x,y,y)=y$$a=0$$\mathrm{Maj}$ -Tor ist unendlich . Ich habe daher den Eindruck, dass sich die verlinkte Arbeit nur mit Rechenschaltungen befasst, die Funktionen mit kleinen endlichen Bereichen wie berechnen . Dann ist in der Tat leicht durch eine arithmetische Schaltung zu berechnen. Aber was ist, wenn ? $f:\mathbb{R}^n\to Y$$Y$$Y=\{0,1\}$$\mathrm{Maj}:Y^m\to Y$$Y=\mathbb{R}$

---

Korrektur [6.03.2017]: Pascal Koiran (einer der Autoren dieses Artikels) wies mich darauf hin, dass ihr Modell leistungsfähiger ist als nur arithmetische Schaltungen: Sie erlauben Sign-Gates (Ausgabe von oder je nachdem, ob die Eingabe negativ ist oder nicht) nicht). Also, die Voting - Funktion Maj kann in diesem Modell simuliert werden, und ich nehme meine „Verwirrung“ zurück.$0$$1$

---

Im Kontext der dynamischen Programmierung ist die gleiche Frage für tropische Min-Plus- und Max-Plus-Semirings besonders interessant und .$(\mathbb{N}\cup\{+\infty\}, \min, +, +\infty,0)$$(\mathbb{N}\cup\{-\infty\}, \max, +, -\infty,0)$

Frage 2: Hält über tropischen semirings? $\mathrm{BPP}\subseteq \mathrm{P/poly}$

Wird in diesen beiden Abschnitten , bedeutet dies, dass die Zufälligkeit sogenannte "reine" dynamische Programmieralgorithmen nicht beschleunigen kann! Diese Algorithmen verwenden in ihren Rekursionen nur Min / Max- und Summenoperationen. Bellman-Ford, Floyd-Warshall, Held-Karp und viele andere bekannte DP-Algorithmen sind rein. $\mathrm{BPP}\subseteq \mathrm{P/poly}$

Bisher kann ich Frage 2 (bejahend) unter dem einseitigen nur beantworten , wenn wir zusätzlich über den min- Plus-Semiring (Minimierung) oder über dem Maximum-Plus-Semiring (Maximierung). Das heißt, wir fordern jetzt, dass die randomisierte tropische Schaltung niemals einen besseren als den optimalen Wert erzeugen kann; Es kann sich jedoch irren, indem es einige schlechtere als optimale Werte angibt. Meine Fragen beziehen sich jedoch auf das zweiseitige Fehlerszenario.$\mathrm{Pr}[\mathsf{C}(x) < f(x)]=0$$\mathrm{Pr}[\mathsf{C}(x) > f(x)]=0$

---

PS [hinzugefügt am 27.02.2017]: Hier ist mein Versuch, Frage 1 zu beantworten (bejahend). Die Idee ist, eine einfachste Version des "kombinatorischen Nullstellensatzes" mit einer Schätzung für das Zarankiewicz-Problem für n-partite Hypergraps aufgrund von Erdos und Spencer zu kombinieren. Modulo dieses letztgenannten Ergebnisses ist das gesamte Argument elementar.

Beachten Sie, dass Frage 2 noch offen bleibt: Der "naive Nullstellensatz" (zumindest in der von mir verwendeten Form) gilt nicht für tropische Semirings.

Dies ist nur eine teilweise Antwort auf Ihre allgemeine Frage (ich bin nicht sicher, was eine vollständig allgemeine Formulierung sein würde), aber es legt nahe, dass das Arbeiten über ausreichend schöne unendliche Halbbilder unter Beschränkung der Zufälligkeit auf einen endlichen Bereich die Frage, ob tatsächlich trivialisieren könnte Der Satz von Adleman gilt.

Angenommen, Sie arbeiten über die komplexen Zahlen , sodass Schaltkreise Polynome über dieses Feld berechnen, und nehmen an, dass die Funktion f selbst durch ein Polynom (wie kompliziert auch immer) der x- Variablen berechnet wird. Dann stellt sich heraus, dass bereits für einige feste r , C ( x , r ) = f ( x ) . Der Grund ist, dass für jedes r die Menge von x mit C ( x , r ) = f ( x ) eine mit Zariski abgeschlossene Teilmenge von bestimmt$\mathbb{C}$$f$$x$$r$$C(x,r) = f(x)$$r$$x$$C(x,r) = f(x)$ muss also alles von C n sein , oder auch eine Teilmenge des Maßes Null. Wenn alle diese Mengen das Maß Null haben würden, dann hättedie Menge vonxmit∃r:C(x,r)=f(x)auch das Maß Null, da nur endlich vielersin Betracht gezogen werden. Auf der anderen Seiteimpliziertdie Annahme, dassCfberechnet, dass die Menge vollständig aus C n bestehen muss , sodass es kein Maß Null geben kann.$\mathbb{C}^n$$\mathbb{C}^n$$r$$x$$\exists r : C(x,r) = f(x)$$C$$f$$\mathbb{C}^n$