Теорема Адлемана о бесконечных полуколец?

В 1978 году Адлеман показал, что $\mathrm{BPP}\subseteq \mathrm{P/poly}$ : если булева функция $f$ из $n$ переменных может быть вычислена с помощью вероятностной булевой схемы размера $M$ , тогда $f$ может быть вычислена с помощью детерминированной булевой схемы размера многочлен от $M$ и $n$ ; на самом деле, размером $O(nM)$ .

Общий Вопрос: За каким другими (чем булевыми) полукольца делает $\mathrm{BPP}\subseteq \mathrm{P/poly}$ трюма?

Чтобы быть более конкретным, вероятностная схема над полукольцом ( S , + , ⋅ , 0 , 1 ) использует свои операции «сложения» ( + ) и «умножения» ( ⋅ ) в качестве затворов. Входы - это входные переменные x 1 , ... , х п , и , возможно , некоторое количество дополнительных случайных величин, которые принимают значения 0 и 1 независимо друг от друга с вероятностью 1 / 2 ; здесь$\mathsf{C}$$(S,+,\cdot,0,1)$$(+)$$(\cdot)$$x_1,\ldots,x_n$$0$$1$$1/2$ и 1 - аддитивная и мультипликативная тождества полукольца соответственно, такая схема C вычисляетзаданную функцию f : S n$0$$1$$\mathsf{C}$ , если для каждого х ∈ S п , Р г [ С ( х ) = е ( х ) ] ≥ 2 / 3 . $f:S^n\to S$$x\in S^n$$\mathrm{Pr}[\mathsf{C}(x)=f(x)]\geq 2/3$

Функция голосования из m переменных является частичной функцией, значение которой равно y, если элемент y появляется более чем в m / 2 раза среди y 1 , … , y m и не определен , если такого элемента у не существует. Простое применение черновских и союзных границ дает следующее.$\mathrm{Maj}(y_1,\ldots,y_m)$$m$$y$$y$$m/2$$y_1,\ldots,y_m$$y$

Уловка большинства: если вероятностная схема вычисляет функцию f : S n → S на конечном множестве X ⊆ S n , то существует m = O ( log | X | ) реализаций C 1 , … , C m из C, таких что f ( x ) = M a j ( C 1 ( x ) , $\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$

Для логического полукольца функция голосования является мажоритарной функцией и имеет небольшие (даже монотонные) цепи. Итак, из теоремы Адлемана следует, что X = { 0 , 1 } n . $\mathrm{Maj}$$X=\{0,1\}^n$

Но как насчет других (особенно бесконечных) полуколец? А как насчет арифметического полукольца (с обычным сложением и умножением)?$(\mathbb{N},+,\cdot,0,1)$

Вопрос 1: Имеют ли трюма над арифметическим полукольцом? $\mathrm{BPP}\subseteq \mathrm{P/poly}$

Хотя я держу пари на «да», я не могу показать это.

Remark: I am aware of this paper where the authors claim $\mathrm{BPP}\subseteq \mathrm{P/poly}$ over the real field $(\mathbb{R},+,\cdot,0,1)$. They deal with non-monotone arithmetic circuits, and also arrive (in Theorem 4) to circuits with the voting function $\mathrm{Maj}$ as an output gate. But how to simulate this $\mathrm{Maj}$-gate by an arithmetic circuit (be it monotone or not)? I.e. how to get their Corollary 3?

Actually, the following simple argument told to me by Sergey Gashkov (from Moscow University) seems to show that this is impossible (at least for circuits able to compute only polynomials). Suppose we can express $\mathrm{Maj}(x,y,z)$ as a polynomial $f(x,y,z)=ax+by+cz+ h(x,y,z)$. Then $f(x,x,z)=x$ implies $c=0$, $f(x,y,x)=x$ implies $b=0$, and $f(x,y,y)=y$ implies $a=0$. This holds because, over fields of zero characteristic, equality of polynomial-functions means equality of coefficients. Note that in Question 1, the range of probabilistic circuits, and hence, the domain of the $\mathrm{Maj}$-gate is infinite. I therefore have an impression that the linked paper deals only with arithmetic circuits computing functions $f:\mathbb{R}^n\to Y$ with small finite ranges $Y$, like $Y=\{0,1\}$. Then $\mathrm{Maj}:Y^m\to Y$ is indeed easy to compute by an arithmetic circuit. But what if $Y=\mathbb{R}$?

---

Correction [6.03.2017]: Pascal Koiran (one of the authors of this paper) pointed to me that their model is more powerful than just arithmetic circuits: they allow Sign-gates (outputing $0$ or $1$ depending on whether the input is negative of not). So, the voting function Maj can be simulated in this model, and I take back my "confusion".

---

In the context of dynamic programming, especially interesting is the same question for tropical min-plus and max-plus semirings $(\mathbb{N}\cup\{+\infty\}, \min, +, +\infty,0)$ and $(\mathbb{N}\cup\{-\infty\}, \max, +, -\infty,0)$.

Question 2: Does $\mathrm{BPP}\subseteq \mathrm{P/poly}$ hold over tropical semirings?

Held $\mathrm{BPP}\subseteq \mathrm{P/poly}$ in these two semirings, this would mean that randomness cannot speed-up so-called "pure" dynamic programming algorithms! These algorithms only use Min/Max and Sum operations in their recursions; Bellman-Ford, Floyd-Warshall, Held-Karp, and many other prominent DP algorithms are pure.

So far, I can only answer Question 2 (affirmatively) under the one-sided error scenario, when we additionally require $\mathrm{Pr}[\mathsf{C}(x) < f(x)]=0$ over the min-plus semiring (minimization), or $\mathrm{Pr}[\mathsf{C}(x) > f(x)]=0$ over the max-plus semiring (maximization). That is, we now require that the the randomized tropical circuit can never produce any better than optimum value; it can, however, err by giving some worse-than-optimal values. My questions are, however, under the two-sided error scenario.

---

P.S. [added 27.02.2017]: Here is my attempt to answer Question 1 (affirmatively). The idea is to combine a simplest version of the "combinatorial Nullstellensatz" with an estimate for the Zarankiewicz problem for n-partite hypergraps, due to Erdos and Spencer. Modulo this latter result, the entire argument is elementary.

Note that Question 2 still remains open: the "naive Nullstellensatz" (at least in the form I used) does not hold in tropical semirings.

This is only a partial answer to your general question (I'm not sure what a fully general formulation would be), but it suggests that working over sufficiently nice infinite semirings while constraining the randomness to a finite domain might actually trivialize the question of whether Adleman's theorem holds.

Suppose you're working over the complex numbers $\mathbb{C}$, so that circuits compute polynomials over that field, and suppose the function $f$ is itself computed by some polynomial (however complicated) of the $x$ variables. Then it turns out that already for some fixed $r$, $C(x,r) = f(x)$. The reason is that for each $r$, the set of $x$ with $C(x,r) = f(x)$ determines a Zariski-closed subset of $\mathbb{C}^n$, and so must be all of $\mathbb{C}^n$, or else a subset of measure zero. If all of these sets were to have measure zero, then, because there are only finitely many $r$'s in consideration, the set of $x$ where $\exists r : C(x,r) = f(x)$ would also have measure zero. On the other hand, the assumption that $C$ computes $f$ implies this that set must be all of $\mathbb{C}^n$, so it cannot have measure zero.