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}$ $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 . $\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 . $\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? $\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 dziedzina $\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}$ -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}$

Korekta [6.03.2017]: Pascal Koiran (jeden z autorów tego artykułu) wskazał mi, że ich model jest potężniejszy niż tylko obwody arytmetyczne: pozwalają na Bramki Znaków (generując lub zależności od tego, czy wejście jest ujemne nie). Funkcję głosowania Maj można symulować w tym modelu i przywracam swoje „zamieszanie”.

0

$0$

1

$1$

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\}, \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 . $\mathrm{Pr}[\mathsf{C}(x) < f(x)]=0$ $\mathrm{Pr}[\mathsf{C}(x) > f(x)]=0$

PS [dodano 27.02.2017]: Oto moja próba odpowiedzi na pytanie 1 (twierdząco). Chodzi o to, by połączyć najprostszą wersję „kombinatorycznego Nullstellensatz” z oszacowaniem problemu Zarankiewicza dla hipergrapów n-partyjnych, spowodowanych Erdosem i Spencerem. Modulo ten ostatni wynik, cały argument jest elementarny.

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.

— Stasys
źródło

nit: BPP jest jednolitą klasą zdefiniowaną za pomocą PTM, a nie obwodów.

— Kaveh

@Kaveh: tak, w tym sensie wynik Adlemana jest nawet nieco silniejszy, nawet w przypadku BPP / poly.

— Stasys

Nie widzę, jak prosty argument pokazuje niemożliwość ... wydaje się, że pokazuje, że współczynniki monomianów x, y i z muszą wynosić zero ... Czego mi brakuje? Ponadto, jeśli wielomian nie może obliczyć Maja, w jaki inny sposób możesz reprezentować obliczenie w ciągu semiery? (Co innego oprócz wielomianu podczas semowania?) Intuicyjnie, w nieskończonej domenie, każde ograniczenie na pewnym y (wymuszając, że na> m / 2 lat musisz wyprowadzić y) wydaje się „niezależne” od innych (żaden podzbiór ograniczeń nie implikuje inny), więc wydaje się, że żaden „skończony” wielomian nie spełnia nieskończenie wielu niezależnych ograniczeń.

— Ryan Williams

@ Ryan: tak, pokazuje to tylko f = Maj oznacza h = Maj. Ale h ma stopień> 1, więc h (x, x, z) = x jest niemożliwe. I masz rację: obwody nad półirowaniami nie mogą obliczyć niczego innego jako wielomianów. Nie mogą więc obliczyć Maj. Ale autorzy tego artykułu zajmują się obwodami {+, x, -, /}, ze wszystkimi operacjami polowymi. Być może wtedy Maj można jeszcze jakoś obliczyć? (Nie wiem jednak, jak to zrobić). Btw zamiast próbować symulować sam Maj, można odpowiedzieć na pytania Q1 i Q2, pokazując, że jedna bramka Maj nie może znacznie zmniejszyć rozmiaru obwodu (co jest całkiem prawdopodobne).

— Stasys

@ Ryan: PS Igor Siergiejew zauważył, że Maj „może” być prawdopodobnie obliczony na podstawie (R, +, x, -, /). Np. Maj (x, y, z) oblicza się przez f (x, y, z) = (xy + xz-2yz) / (2x-yz) dla wszystkich danych wejściowych z | {x, y, z} | = 2. Zauważ, że powyższy prosty argument oznacza, że już na takich danych wejściowych nie można tego zrobić (R, +, x, -). Tak więc podział może pomóc. Ale mamy do czynienia z podziałem według numeru 0 ...

— Stasys

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 $\mathbb{C}$ $f$ $x$ $r$ $C(x,r) = f(x)$ $r$ $x$ $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$

— Andrew Morgan
źródło

Ciekawy. Mówiąc bardziej ogólnie, obwód probabilistyczny o wielkości M jest jakąś losową zmienną C, przyjmującą swoje wartości w zbiorze wszystkich obwodów (tego typu) z co najwyżej M bramkami. [Przy okazji tego artykułu Cuckera z al. pozwala na dowolną dystrybucję C. Stil „większościowy trick” działa.] Czy mogę wywnioskować z twojego argumentu, że jeśli zakres C jest skończony, to twierdzenie Adlemana jest trywialne, gdy podzbiory zamknięte w Zawińskim są albo trywialne (same zbiory), albo mają zerową miarę? Czy mamy ten efekt „wszystko albo nic” w tropikalnych półprzezroczystościach? (Interesuję się nimi głównie.)

— Stasys

Przepraszam, nie wiem jak lub czy argument uogólniałby się na inne półprzezroczystości. Jedną z głównych rzeczy, których mi brakuje (dla mnie) jest intuicja geometryczna podobna do tego, w jaki sposób „wielomiany, które się nie zgadzają” przekładają się na „podzbiory miara zera ”. W szczególności w przypadku tropikalnych półksiężyców operacje wydają się tak odmienne od zwykłych wielomianów, że trudno nawet zgadnąć, jaka powinna być odpowiednia adaptacja.

C^{n}

$\mathbb{C}^n$

— Andrew Morgan