Teorema de Adleman sobre infinitos semirings?

Adleman demonstrou, em 1978, que $\mathrm{BPP}\subseteq \mathrm{P/poly}$ : se uma função booleana de variáveis pode ser calculado por um circuito booleano probabilística de tamanho , em seguida, pode também ser calculado por um circuito booleano determinista de tamanho polinômio em e ; na verdade, do tamanho . n M f M n O ( n M $f$$n$$M$$f$$M$$n$$O(nM)$

Pergunta geral: Sobre quais outras semi-séries (que não sejam booleanas) são válidas ? $\mathrm{BPP}\subseteq \mathrm{P/poly}$

Para ser um pouco mais específico, um circuito probabilístico em um semiring usa suas operações de "adição" e "multiplicação '' como portas As entradas são variáveis ​​de entrada e possivelmente algum número de variáveis ​​aleatórias adicionais, que assumem os valores e independentemente com probabilidade ; aqui e são, respectivamente, as identidades aditiva e multiplicativa da semicondução Esse circuito calcula uma dada função ( 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$se para cada , . P r [ C ( x ) = f ( x ) ] ≥ 2 /$x\in S^n$$\mathrm{Pr}[\mathsf{C}(x)=f(x)]\geq 2/3$

A função de votação de variáveis ​​é uma função parcial cujo valor é se o elemento aparecer mais de vezes entre e é indefinido , se esse elemento existir. Uma aplicação simples dos limites de Chernoff e da união produz o seguinte.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$

Truque de Maioria: Se um circuito probabilístico calcula uma função em um conjunto finito , então existem realizações C 1 , … , C m de C tal que f ( x ) = M a j ( C 1 ( x ) , … , C m ( x f : S n → S X ⊆ S n m = O ( log | X |$\mathsf{C}$$f:S^n\to S$$X\subseteq S^n$$m=O(\log|X|)$$C_1,\ldots,C_m$$\mathsf{C}$ é válido para todos os x ∈ X . $f(x)=\mathrm{Maj}(C_1(x),\ldots,C_m(x))$$x\in X$

Durante o semicondutor booleano, a função de votação é a função majoritária e possui circuitos pequenos (mesmo monótonos). Então, o teorema de Adleman segue tomando X $\mathrm{Maj}$ . $X=\{0,1\}^n$

Mas e quanto a outras semirrings (especialmente infinitas)? E o semicondutor aritmético (com adição e multiplicação usuais)?$(\mathbb{N},+,\cdot,0,1)$

Pergunta 1: Does domínio sobre o semiring aritmética? $\mathrm{BPP}\subseteq \mathrm{P/poly}$

Apesar de eu apostar em "sim", não posso mostrar isso.

Nota: Estou ciente deste papel , onde os autores afirmam sobre o campo reais ( R , + , ⋅ , 0 , 1 ) . Eles lidam com circuitos aritméticos não monótonos e também chegam (no Teorema 4) a circuitos com a função de votação M a j como uma porta de saída. Mas como simular essa porta M a j por um circuito aritmético (seja monótono ou não)? Ou seja, como obter o seu corolário 3?$\mathrm{BPP}\subseteq \mathrm{P/poly}$$(\mathbb{R},+,\cdot,0,1)$$\mathrm{Maj}$$\mathrm{Maj}$

Na verdade, o argumento simples a seguir me contado por Sergey Gashkov (da Universidade de Moscou) parece mostrar que isso é impossível (pelo menos para circuitos capazes de calcular apenas polinômios ). Suponha que possamos expressar como um polinômio f ( x , y , z ) = a x + b y + c z + h ( x , y , z ) . Então f $\mathrm{Maj}(x,y,z)$$f(x,y,z)=ax+by+cz+ h(x,y,z)$ implica c = 0 , f ( x , y , x ) = x implica b = 0 , e f ( x , y , y ) = y implica a = 0 . Isso ocorre porque, sobre campos de característica zero, igualdade de funções polinomiais significa igualdade de coeficientes. Observe que na pergunta 1, a faixa de circuitos probabilísticos e, portanto, o domínio do$f(x,x,z)=x$$c=0$$f(x,y,x)=x$$b=0$$f(x,y,y)=y$$a=0$ porta- j éinfinita. Portanto, tenho a impressão de que o artigo vinculado lida apenas com funções aritméticas de computação de circuitos f : R n → Y com pequenos intervalos finitos Y , como Y = {é realmente fácil de calcular por um circuito aritmético. Mas e se Y = R ? $\mathrm{Maj}$$f:\mathbb{R}^n\to Y$$Y$ . Então M a j : Y m → $Y=\{0,1\}$$\mathrm{Maj}:Y^m\to Y$$Y=\mathbb{R}$

---

Correção [6.03.2017]: Pascal Koiran (um dos autores deste artigo) apontou para mim que o modelo deles é mais poderoso do que apenas circuitos aritméticos: eles permitem portas de sinal (saída ou 1, dependendo de a entrada ser negativa). não). Portanto, a função de votação Maj pode ser simulada neste modelo, e retiro minha "confusão".$0$$1$

---

No contexto da programação dinâmica, é especialmente interessante a mesma pergunta para semirrubas tropicais min-plus e max-plus e ( N ∪ { - ∞ } , max , + $(\mathbb{N}\cup\{+\infty\}, \min, +, +\infty,0)$ .$(\mathbb{N}\cup\{-\infty\}, \max, +, -\infty,0)$

Pergunta 2: Does domínio sobre semirings tropicais? $\mathrm{BPP}\subseteq \mathrm{P/poly}$

Retido nestes dois semirings, isso significaria que a aleatoriedade não pode velocidade até os chamados "puros" algoritmos de programação dinâmica! Esses algoritmos usam apenas as operações Min / Max e Sum em suas recursões; Bellman-Ford, Floyd-Warshall, Held-Karp e muitos outros algoritmos de DP proeminentessãopuros. $\mathrm{BPP}\subseteq \mathrm{P/poly}$

Até o momento, só posso responder à pergunta 2 (afirmativamente) no cenário de erro unilateral , quando exigimos adicionalmente durante o semiring min-plus (minimização) ou P r [ C ( x ) > $\mathrm{Pr}[\mathsf{C}(x) < f(x)]=0$$\mathrm{Pr}[\mathsf{C}(x) > f(x)]=0$sobre a semiring max-plus (maximização). Ou seja, agora exigimos que o circuito tropical aleatório nunca possa produzir um valor melhor que o ótimo; pode, no entanto, errar ao fornecer alguns valores piores que os ótimos. Minhas perguntas estão, no entanto, no cenário de erro nos dois lados .

---

PS [adicionado em 27.02.2017]: Aqui está minha tentativa de responder à pergunta 1 (afirmativamente). A idéia é combinar uma versão mais simples da "Nullstellensatz combinatória" com uma estimativa para o problema de Zarankiewicz para hipergraps de n-partidos, devido a Erdos e Spencer. Módulo este último resultado, todo o argumento é elementar.

Observe que a pergunta 2 ainda permanece em aberto: o "Nullstellensatz" ingênuo (pelo menos na forma que eu usei) não se aplica aos semirriscos tropicais.

Esta é apenas uma resposta parcial à sua pergunta geral (não tenho certeza de qual seria uma formulação totalmente geral), mas sugere que trabalhar em semirings infinitas suficientemente agradáveis ​​enquanto restringe a aleatoriedade a um domínio finito pode realmente banalizar a questão de saber se O teorema de Adleman é válido.

Suponha que você esteja trabalhando com os números complexos , para que os circuitos computem polinômios sobre esse campo e suponha que a função f seja ela própria calculada por algum polinômio (por mais complicado que seja) das variáveis x . Acontece que já para algum r fixo , C ( x , r ) = f ( x ) . A razão é que, para cada r , o conjunto de x com C ( x , r ) = f ( x ) determina um subconjunto fechado de Zariski de$\mathbb{C}$$f$$x$$r$$C(x,r) = f(x)$$r$$x$$C(x,r) = f(x)$ , e assim devem ser todas de C n , ou então um subconjunto de medida nula. Se todos esses conjuntos tivessem a medida zero, então, porque há apenasrfinitosem consideração, o conjunto dexonde∃r:C(x,r)=f(x)também teria a medida zero. Por outro lado, o pressuposto de queCcalculafimplica esse esse conjunto deve ser tudo de C n , por isso não pode ter medida zero.$\mathbb{C}^n$$\mathbb{C}^n$$r$$x$$\exists r : C(x,r) = f(x)$$C$$f$$\mathbb{C}^n$