Czy BPP vs. P to prawdziwy problem po tym, jak wiemy, że BPP leży w P / poly?

My wiemy (teraz około 40 lat, dzięki Adleman, Bennet Gill), że włączenie BPP $\subseteq$ P / poly, i jeszcze silniejszy BPP / poli $\subseteq$ P / poli trzymaj. „/ Poly” oznacza, że ​​pracujemy nierównomiernie (osobny obwód dla każdej długości wejściowej $n$ ), podczas gdy P bez tego „/ poly” oznacza, że ​​mamy jedną maszynę Turinga dla wszystkich możliwych długości wejściowych $n$ , nawet dłuższych niż, powiedzmy, $n$ = liczba sekund do następnego „Wielkiego Wybuchu”.

Pytanie 1: Jakie nowe dowody (lub odrzucenie) BPP = P przyczyniłyby się do naszej wiedzy po poznaniu BPP $\subseteq$ P / poli?

Pod „nowym” mam na myśli wszelkie naprawdę zaskakujące konsekwencje, takie jak załamanie / oddzielenie innych klas złożoności. Porównaj to z konsekwencjami, jakie przyniosłoby dowód / odrzucenie NP $\subseteq$ P / poli.

$\not\subseteq$ 2 o ( n $[2^{O(n)}]$$2^{o(n)}$

Pytanie 2: Dlaczego nie możemy udowodnić BPP = P w podobny sposób, jak dowód BPP / poly P / poly? $\subseteq$

One „oczywiste” przeszkodą jest skończony vs. nieskończony problem domeny: układy logiczne o pracy nad skończone domen, podczas gdy maszyny Turinga pracować nad całą zbiór $\{0,1\}^*$ od $0$ - $1$ ciągi o dowolnej długości. Tak więc, aby zdandomizować probabilistyczne obwody boolowskie, wystarczy wziąć większość niezależnych kopii obwodu probabilistycznego i zastosować nierówność Chernoffa wraz z związkami. Oczywiście w przypadku domen nieskończonych ta prosta zasada większości nie będzie działać.

Ale czy ta (nieskończona domena) jest prawdziwą „przeszkodą”? Dzięki zastosowaniu wyników uczenia statystycznej teorii (wymiar VC), już można udowodnić, że BPP / poli P / poli posiada również dla obwodów pracujących nad nieskończonych domen, takich jak obwody arytmetycznych (pracujących na wszystkich liczb rzeczywistych); patrz np. ten artykuł Cuckera przy al. Korzystając z podobnego podejścia, wszystko, czego potrzebujemy, to pokazać, że wymiar VC wielozadaniowych maszyn Turinga nie może być zbyt duży. Czy ktoś widział jakiekolwiek próby wykonania tego ostatniego kroku? $\subseteq$

Wyniki (znane jako równomierna zbieżność prawdopodobieństwa ) sugerują zatem, co następuje: jeśli dla każdego wejścia losowo wybrana funkcja (przy pewnym rozkładzie prawdopodobieństwa na ) spełnia dla stałej , następnie można obliczyć na wszystkich wejściach jako większość niektóre (stały) z funkcji . Patrz np. Corollary 2 w pracy Hausslera . [Aby tak się stało, istnieją pewne łagodne warunki mierzalności na ] $x\in X$$\mathbf{f}\in F$$F$$\mathrm{Prob}\{\mathbf{f}(x)=f(x)\}\geq 1/2+c$$c>0$$f(x)$$x\in X$$m=O(v)$$F$$F$

Na przykład, jeśli jest zbiorem wszystkich wielomianów obliczalnych przez obwody arytmetyczne o rozmiarze , wówczas wszystkie wielomiany w mają stopień co najwyżej . Stosując znane górne granice liczby zerowych wzorów wielomianów (patrz np. Ten artykuł ), można pokazać, że wymiar VC dla wynosi . Oznacza to włączenie BPP / poly P / poly dla obwodów arytmetycznych.f : R n → R ≤ s F D = 2 s F O ( n log D ) = O ( n s ) $F$$f:\mathbb{R}^n\to\mathbb{R}$$\leq s$$F$$D=2^s$$F$$O(n\log D)=O(ns)$$\subseteq$

Nie jestem pewien, jaka to odpowiedź, po prostu pobłażam sobie.

Pytanie 1 można równie dobrze zadać na temat P NP i z podobną odpowiedzią - techniki / pomysły zastosowane w celu udowodnienia wyniku byłyby wielkim przełomem bardziej niż sam wniosek.$\neq$

W przypadku pytania 2 chcę podzielić się pewnym doświadczeniem i przemyśleniem. O ile mi wiadomo, wszystkie techniki i pomysły dotyczące BPP = P przechodzą przez „derandomizację”: biorąc pod uwagę dowolną probabilistyczną maszynę polityczną Turinga, skonstruuj PRG, aby dostarczyć mu kilka deterministycznie wybranych bitów zamiast losowych takie, że jego zachowanie jest bardzo podobne do zachowania na naprawdę losowych bitach. Zatem przy wystarczająco dobrych generatorach pseudolosowych otrzymujemy BPP = P. („Świat BPP = P” Goldreicha dowodzi, że każdy dowód BPP = P musi się z tym równać.)

Jest to w zasadzie podobne do BPP P / poly, z tym wyjątkiem, że PRG jest ciągiem porad wytwarzanym przez magię. Być może najlepszą odpowiedzią na twoje pytanie 2 jest to, że w P nie mamy żadnej magii i sami musimy wymyślić szereg porad. Derandomizacja jest także ideą wynikającą z 2004 r. SL = L, przy użyciu narzędzi takich jak wykresy ekspanderów.$\subseteq$

Teraz zastanów się, co taki dowód oznaczałby tylko dla jednego konkretnego algorytmu, testu pierwotności Millera-Rabina. Wskazuje to na istnienie jakiegoś deterministycznego generatora, który wybiera sekwencję liczb całkowitych do zasilenia testu pierwotności Millera-Rabina w taki sposób, że jeśli i tylko jeśli wszystkie liczby całkowite miną, to pierwotna liczba była pierwsza.

Jak rozumiem (choć nie jestem ekspertem), pytanie, czy taka lista istnieje i jak małe mogą być liczby w niej (w szczególności, czy wystarczy sprawdzić wszystkie liczby poniżej pewnego ograniczenia), wydaje się dość głębokim pytaniem w teoria liczb i jest ściśle związana z dowodzeniem form uogólnionej hipotezy Riemanna. Zobacz to pytanie . Nie sądzę, by miało to formalne implikacje, ale wydaje się, że nie wydaje się to czymś, co spodziewamy się w przyszłym tygodniu jako przypadkowa miniaturowa konsekwencja znacznie bardziej ogólnej konstrukcji PRG.