Théorème d'Adleman sur des demi-tours infinis?

Adleman a montré en 1978 que $\mathrm{BPP}\subseteq \mathrm{P/poly}$ : si une fonction booléenne $f$ de $n$ variables peut être calculée par un circuit booléen probabiliste de taille $M$ , alors $f$ peut également être calculé par un circuit booléen déterministe de taille polynôme en $M$ et $n$ ; en fait, de taille $O(nM)$ .

Question générale: sur quels autres semirings (autres que booléens) $\mathrm{BPP}\subseteq \mathrm{P/poly}$ tient-il?

Pour être un peu plus précis, un circuit probabiliste sur un semi-câblage ( S , + , ⋅ , 0 , 1 ) utilise ses opérations "d'addition" ( + ) et de "multiplication" ( ⋅ ) comme portes. Les entrées sont des variables d'entrée x 1 , ... , x n et , éventuellement , un certain nombre de variables aléatoires supplémentaires, qui prennent les valeurs 0 et 1 , indépendamment , avec une probabilité 1 / 2 ; ici$\mathsf{C}$$(S,+,\cdot,0,1)$$(+)$$(\cdot)$$x_1,\ldots,x_n$$0$$1$$1/2$ et 1 sont respectivement les identités additive et multiplicative du semirage. Un tel circuit C calculeune fonction donnée f : S $0$$1$$\mathsf{C}$ si pour tout x ∈ S n , P r [ C ( x ) = f ( x ) ] ≥ 2 / trois . $f:S^n\to S$$x\in S^n$$\mathrm{Pr}[\mathsf{C}(x)=f(x)]\geq 2/3$

La fonction de vote de m variables est une fonction partielle dont la valeur est y si l'élément y apparaît supérieur à m /$\mathrm{Maj}(y_1,\ldots,y_m)$$m$$y$$y$$m/2$ fois parmi les et n'est pas défini , si un tel élément y n'existe pas. Une simple application des limites de Chernoff et de l'union donne les résultats suivants.$y_1,\ldots,y_m$$y$

Truc de la majorité: Si un circuit probabiliste calcule une fonction f : S n → S sur un ensemble fini X ⊆ S n , alors il y a m = O ( log | X | ) réalisations C 1 , … , C m de C telles que 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}$ est vrai pour tout x ∈ X . $f(x)=\mathrm{Maj}(C_1(x),\ldots,C_m(x))$$x\in X$

Au cours du semi-booléen, la fonction de vote est la fonction majoritaire et a de petits circuits (même monotones). Ainsi, le théorème d'Adleman suit en prenant X = { 0 , 1 } n . $\mathrm{Maj}$$X=\{0,1\}^n$

Mais qu'en est-il des autres semirings (surtout, infinis)? Qu'en est-il de la semi- arithmétique (avec addition et multiplication habituelles)?$(\mathbb{N},+,\cdot,0,1)$

Question 1: Est-ce que emprise sur le semi - anneau arithmétique? $\mathrm{BPP}\subseteq \mathrm{P/poly}$

Bien que je parie pour "oui", je ne peux pas le montrer.

Remarque: Je connais cet article où les auteurs réclament sur le champ réel ( R , + , ⋅ , 0 , 1 ) . Ils traitent des circuits arithmétiques non monotones et arrivent également (dans le théorème 4) à des circuits avec la fonction de vote M a j comme porte de sortie. Mais comment simuler ce M a j -gate par un circuit arithmétique (monotone ou non)? C'est-à-dire comment obtenir leur corollaire 3?$\mathrm{BPP}\subseteq \mathrm{P/poly}$$(\mathbb{R},+,\cdot,0,1)$$\mathrm{Maj}$$\mathrm{Maj}$

En fait, l'argument simple suivant qui m'a été dit par Sergey Gashkov (de l'Université de Moscou) semble montrer que cela est impossible (au moins pour les circuits capables de calculer uniquement des polynômes ). Supposons que nous pouvons exprimer comme un polynôme f ( x , y , z ) = a x + b y + c z + h ( x , y , z ) . Alors f $\mathrm{Maj}(x,y,z)$$f(x,y,z)=ax+by+cz+ h(x,y,z)$ implique c = 0 , f ( x , y , x ) = x implique b = 0 et f ( x , y , y ) = y implique a = 0 . Cela tient parce que, sur des champs de caractéristique nulle, l'égalité des fonctions polynomiales signifie l'égalité des coefficients. Notez que dans la question 1, la gamme de circuits probabilistes, et donc le domaine du$f(x,x,z)=x$$c=0$$f(x,y,x)=x$$b=0$$f(x,y,y)=y$$a=0$ -gate estinfini. J'ai donc l'impression que l'article lié ne traite que des circuits arithmétiques calculant les fonctions f : R n → Y avec de petites plages finies Y , comme Y = { 0 , 1 } . Alors M a j : Y m → Y est en effet facile à calculer par un circuit arithmétique. Et si Y = R ? $\mathrm{Maj}$$f:\mathbb{R}^n\to Y$$Y$$Y=\{0,1\}$$\mathrm{Maj}:Y^m\to Y$$Y=\mathbb{R}$

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.

Jusqu'à présent, je ne peux répondre à la question 2 (affirmativement) que dans le scénario d'erreur unilatérale , lorsque nous avons en outre besoin de sur le semiring min-plus (minimisation), ou P r [ C ( x ) > f ( x ) ] = $\mathrm{Pr}[\mathsf{C}(x) < f(x)]=0$$\mathrm{Pr}[\mathsf{C}(x) > f(x)]=0$sur le semiring max-plus (maximisation). Autrement dit, nous exigeons maintenant que le circuit tropical randomisé ne puisse jamais produire mieux que la valeur optimale; il peut cependant se tromper en donnant des valeurs pires qu'optimales. Mes questions relèvent cependant du scénario d' erreur bilatéral .

Notez que la question 2 reste ouverte: la "Nullstellensatz naïve" (du moins sous la forme que j'ai utilisée) ne tient pas dans les demi-semelles tropicales.

Ce n'est qu'une réponse partielle à votre question générale (je ne suis pas sûr de ce que serait une formulation entièrement générale), mais cela suggère que travailler sur des demi-tours infinis suffisamment agréables tout en contraignant le caractère aléatoire à un domaine fini pourrait en fait banaliser la question de savoir si Le théorème d'Adleman tient.

$\mathbb{C}$$f$$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.