Twierdzenie Adlemana o nieskończonych półkolach?

Adleman wykazały w 1978 r : Jeżeli logiczna funkcja o zmiennych może być obliczany za pomocą prawdopodobieństwa logicznego obwodu o rozmiarze , a następnie może być obliczany za pomocą deterministycznych obwód boolowski wielomianu wielkości w i ; właściwie o wielkości . $\mathrm{BPP}\subseteq \mathrm{P/poly}$$f$$n$$M$$f$$M$$n$$O(nM)$

Pytanie ogólne: W stosunku do innych (boolowskich) semiringów ? $\mathrm{BPP}\subseteq \mathrm{P/poly}$

Mówiąc ściślej, obwód probabilistyczny w trakcie semirowania używa operacji „dodawania” i „mnożenia” jako bramek Dane wejściowe to zmienne wejściowe i ewentualnie pewna liczba dodatkowych zmiennych losowych, które przyjmują wartości i niezależnie z prawdopodobieństwem ; tutaj i są odpowiednio addytywną i multiplikatywną tożsamością semirowania Taki obwód oblicza daną funkcję$\mathsf{C}$$(S,+,\cdot,0,1)$$(+)$$(\cdot)$$x_1,\ldots,x_n$$0$$1$$1/2$$0$$1$$\mathsf{C}$ x ∈ S N P r [ C ( x ) = f ( x ) ] ≥ 2 /$f:S^n\to S$jeśli dla każdego , . $x\in S^n$$\mathrm{Pr}[\mathsf{C}(x)=f(x)]\geq 2/3$

Funkcja głosu z zmiennych jest częściowo funkcją, której wartość jest , gdy element występuje więcej niż razy wśród i jest zdefiniowana , jeśli nie istnieje taki element . Proste zastosowanie granic Chernoffa i związków daje następujące.$\mathrm{Maj}(y_1,\ldots,y_m)$$m$$y$$y$$m/2$$y_1,\ldots,y_m$$y$

Większość trick: Jeśli obwód probabilistyczny wylicza funkcji na skończonego zbioru , a następnie jest realizacje o tak, że odnosi się do wszystkich . f : S n → S X ⊆ S n m = O ( log | X | ) C 1 , … , C m C f ( x ) = M a j ( C 1 ( x ) , … , C m ( x ) ) 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$

W ciągu semestru boolowskiego funkcja głosowania jest funkcją większościową i ma małe (nawet monotoniczne) obwody. Tak więc twierdzenie Adlemana następuje po przyjęciu . X = { 0 , 1 } $\mathrm{Maj}$$X=\{0,1\}^n$

A co z innymi (zwłaszcza nieskończonymi) półksiężycami? Co z arytmetykiem semiring (ze zwykłym dodawaniem i mnożeniem)?$(\mathbb{N},+,\cdot,0,1)$

Pytanie 1: Czy utrzymuje się nad semirowaniem arytmetycznym? $\mathrm{BPP}\subseteq \mathrm{P/poly}$

Chociaż stawiam na „tak”, nie mogę tego pokazać.

Uwaga: Znam ten artykuł, w którym autorzy twierdzą, że w prawdziwym polu . Mają do czynienia z niemonotonicznymi obwodami arytmetycznymi, a także docierają (w Twierdzeniu 4) do obwodów z funkcją głosowania jako bramką wyjściową. Ale jak zasymulować ten matematyczny-drzwi przez obwód arytmetyczny (monotoniczny czy nie)? Tj. Jak zdobyć Corollary 3? ( R , + , ⋅ , 0 , 1 ) M a j M a $\mathrm{BPP}\subseteq \mathrm{P/poly}$$(\mathbb{R},+,\cdot,0,1)$$\mathrm{Maj}$$\mathrm{Maj}$

Właściwie następujący prosty argument podany mi przez Siergieja Gaszkowa (z Uniwersytetu Moskiewskiego) wydaje się wskazywać, że jest to niemożliwe (przynajmniej w przypadku obwodów zdolnych do obliczania tylko wielomianów ). Załóżmy, że możemy wyrazić jako wielomian . Następnie oznacza , oznacza , a oznacza . Dzieje się tak, ponieważ ponad polami o charakterystyce zerowej równość funkcji wielomianowych oznacza równość współczynników. Zauważ, że w pytaniu 1 zakres obwodów probabilistycznych, a tym samym dziedzinaf ( x , y , z ) = a x + b y + c z + h ( x , y , z ) f ( x , x , z ) = x c = 0 f ( x , y , x ) = x b $\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$f ( x , y , y ) = y a = 0 M a j f : R n → Y Y Y = { 0 , 1 } M a j : Y m → Y Y = $b=0$$f(x,y,y)=y$$a=0$$\mathrm{Maj}$ -gate jest nieskończony . Mam zatem wrażenie, że połączony papier dotyczy tylko funkcji obliczeniowych obwodów arytmetycznych o małych skończonych zakresach , takich jak . Wtedy jest rzeczywiście łatwe do obliczenia za pomocą obwodu arytmetycznego. Ale co jeśli ? $f:\mathbb{R}^n\to Y$$Y$$Y=\{0,1\}$$\mathrm{Maj}:Y^m\to Y$$Y=\mathbb{R}$

W kontekście programowania dynamicznego szczególnie interesujące jest to samo pytanie o tropikalne semirings min-plus i max-plus i (\ mathbb {N} \ cup \ {- \ infty \}, \ max, +, - \ infty, 0) .( N ∪ { - ∞ } , max , + , - ∞ , 0 $(\mathbb{N}\cup\{+\infty\}, \min, +, +\infty,0)$$(\mathbb{N}\cup\{-\infty\}, \max, +, -\infty,0)$

Pytanie 2: Czy przewyższa tropikalne półksiężyca? $\mathrm{BPP}\subseteq \mathrm{P/poly}$

Odbywając w tych dwóch półkolach, oznaczałoby to, że losowość nie może przyspieszyć tak zwanych „czystych” algorytmów programowania dynamicznego! Algorytmy te używają tylko operacji Min / Max i Sum w swoich rekurencjach; Bellman-Ford, Floyd-Warshall, Held-Karp i wiele innych znanych algorytmów DP są czyste. $\mathrm{BPP}\subseteq \mathrm{P/poly}$

Do tej pory mogę odpowiedzieć na pytanie 2 (twierdząco) tylko w przypadku jednostronnego scenariusza błędu, gdy dodatkowo wymagamy ciągu min- plus semirowanie (minimalizacja) lub powyżej maksymalnego semiery (maksymalizacja). Oznacza to, że teraz wymagamy, aby losowy obwód tropikalny nigdy nie wytwarzał wartości lepszej niż optymalna; może jednak popełnić błąd, podając wartości gorsze niż optymalne. Moje pytania dotyczą jednak scenariusza błędu dwustronnego .P r [ C ( x ) > f ( x ) ] = $\mathrm{Pr}[\mathsf{C}(x) < f(x)]=0$$\mathrm{Pr}[\mathsf{C}(x) > f(x)]=0$

Zwróć uwagę, że pytanie 2 wciąż pozostaje otwarte: „naiwny Nullstellensatz” (przynajmniej w takiej formie, w jakiej użyłem) nie dotyczy tropikalnych półksiężyców.

Jest to tylko częściowa odpowiedź na twoje ogólne pytanie (nie jestem pewien, czym byłaby w pełni ogólna formuła), ale sugeruje, że praca nad wystarczająco ładnymi nieskończonymi półirówkami przy ograniczeniu losowości do skończonej domeny może w rzeczywistości trywializować pytanie, czy Twierdzenie Adlemana obowiązuje.

Załóżmy, że pracujesz nad liczbami zespolonymi , aby obwody obliczały wielomiany na tym polu, i załóżmy, że sama funkcja jest obliczana przez jakiś wielomian (choć skomplikowany) zmiennych . Okazuje się, że już dla niektórych stałych , . Powodem jest to, że dla każdego zbiór z określa zamknięty podzbiór Zariski , a więc musi być cały z lub podzbiór miary zero. Gdyby wszystkie te zbiory miały mieć miarę zero, to dlatego, że istnieje tylko skończenie wiele f x r C ( x , r ) = f ( x ) r x C ( x , r $\mathbb{C}$$f$$x$$r$$C(x,r) = f(x)$$r$$x$C n C n r x ∃ r : C ( x , r ) = f ( x ) C f C$C(x,r) = f(x)$$\mathbb{C}^n$$\mathbb{C}^n$$r$biorąc pod uwagę, zbiór gdzie również miałby miarę zerową. Z drugiej strony założenie, że oblicza implikuje, że tym zestawem musi być cały , więc nie może mieć miary zero.$x$$\exists r : C(x,r) = f(x)$$C$$f$$\mathbb{C}^n$