Pytania otagowane jako derandomization

Każdy algorytm zrandomizowany można zasymulować za pomocą algorytmu deterministycznego, kosztem wykładniczego wzrostu czasu działania. Derandomizacja polega na przekształcaniu zrandomizowanych algorytmów w wydajne algorytmy deterministyczne.

1
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 nnn ), podczas gdy P bez tego „/ poly” oznacza, …
1
Bardziej wydajna nierównomierna derandomizacja?
Adleman, FOCS'78 wykazał, że dowolny randomizowany obwód dla wejść o długości może być nierównomiernie derandomizowany. Jednak konstrukcja skutecznie powiela pierwotny obwód razy, więc obwód derandomizowany jest większy niż obwód pierwotny o współczynnik . Czy istnieje bardziej wydajna konstrukcja, która zwielokrotnia rozmiar obwodu przez mniejszy współczynnik?nnnO ( n )O(n)O(n)O ( n …
3
Przykłady udanej derandomizacji z BPP na P.
Jakie są główne przykłady udanej derandomizacji lub przynajmniej postępów w wykazywaniu konkretnych dowodów w kierunku celu (a nie związku losowości z twardością)?P=BPPP=BPPP=BPP Jedyny przykład, jaki przychodzi mi na myśl, to deterministyczne badanie pierwotności wielomianów czasowych AKS (nawet w tym przypadku istniała metodologia zakładająca GRH). Więc jakie konkretne dowody na przykładzie …
1
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 . BPP⊆P/polyBPP⊆P/poly\mathrm{BPP}\subseteq \mathrm{P/poly}fffnnnMMMfffMMMnnnO(nM)O(nM)O(nM) Pytanie ogólne: W stosunku do innych (boolowskich) …
3
Nierówność typu Chernoffa dla niezależnych zmiennych losowych parami
Nierówności typu Chernoffa służą do wykazania, że ​​prawdopodobieństwo, że suma niezależnych zmiennych losowych znacznie odbiega od wartości oczekiwanej, jest wykładniczo małe w wartości oczekiwanej i odchyleniu. Czy istnieje jakakolwiek nierówność typu Chernoffa dla dowolnej sumy niezależnych parami zmiennych losowych? Innymi słowy, czy istnieje wynik, który pokazuje, co następuje: prawdopodobieństwo, że …
2
Jaka jest najgorsza złożoność sita z polem liczbowym?
Biorąc kompozytu Pole numeru sita ogólnie najlepiej znane algorytm faktoryzacji całkowitymi faktoryzacji N . Jest to algorytm randomizowany i otrzymujemy oczekiwaną złożoność O ( e √N∈NN∈NN\in\Bbb NNNNdo współczynnikaN.O(e649√(logN)13(loglogN)23)O(e649(log⁡N)13(log⁡log⁡N)23)O\Big(e^{\sqrt{\frac{64}{9}}(\log N)^{\frac 13}(\log\log N)^{\frac 23}}\Big)NNN Szukałem informacji o złożoności najgorszych przypadków w tym randomizowanym algorytmie. Nie mogę jednak znaleźć informacji. (1) Jaka jest …
2
Niezależni gaussowie parami
Biorąc pod uwagę X1,…,XkX1,…,XkX_1,\ldots,X_k (iid gaussians ze średnią 000 i wariancją 111 ), czy możliwe jest (jak?) Próbkowanie (dla m=k2m=k2m=k^2 ) Y1,…,YmY1,…,YmY_1, \ldots, Y_m takie, że YiYiY_i są parami niezależni gaussowie ze średnią 000 i wariancją 111 .
3
Derandomizacja strumieniowa
Algorytmy strumieniowe wymagają w większości przypadków randomizacji, aby zrobić coś nietrywialnego, a ze względu na ograniczenie małej przestrzeni potrzebują programów PRG, które zajmują mało miejsca. Znam dwie metody, które do tej pory były cytowane w algorytmach strumieniowych: -niezależne PRG-y, takie jak 4-mądra, niezależna rodzina używana przez Alona / Matiasa / …
2
Konsekwencja PIT w stosunku do bez wydajnego algorytmu
Biorąc pod uwagę tak, że współczynniki są ograniczone przez , czy trzymać?p , q B p ≡ qp(x1,…,xn),q(x1,…,xn)∈Z[x1,…,xn]p(x1,…,xn),q(x1,…,xn)∈Z[x1,…,xn]p(x_1,\dots,x_n),q(x_1,\dots,x_n)\in \Bbb Z[x_1,\dots,x_n]p,qp,qp,qBBBp≡qp≡qp\equiv q Obowiązuje tutaj lemat Schwartza-Zippela, ponieważ dotyczy on pól ogólnych i i istnieje skuteczny algorytm losowy dla tego problemu.Z⊂QZ⊂Q\Bbb Z\subset\Bbb Q Oczekujemy, że ten problem będzie miał skuteczną derandomizację. Jakie …
1
Słynny papier P = BPP Impagliazzo i Wigdersona
Czytam słynny artykuł Impagliazzo i Wigdersona w 1997 roku. Ponieważ jestem nowy w tej dziedzinie, a artykuł jest zwięzłą wersją konferencji, mam trudności z podążeniem za nimi. W szczególności niektórym z ich nowych twierdzeń brakuje dowodów. Według mojej najlepszej wiedzy nie opublikowano wersji czasopisma.P = B P PP.=bP.P.\mathsf P=\mathsf{BPP} Szukam …
2
Oszukiwanie
Mam kilka pytań dotyczących oszukiwania obwodów o stałej głębokości. Wiadomo, że -wise niezależności konieczne oszukać A C 0 obwody głębokości D , gdzie n jest wielkości wejściowych. Jak można to udowodnić?logO ( d)( n )logO(d)⁡(n)\log^{O(d)}(n)A C.0AC0AC^0reddnnn Ponieważ powyższe jest prawdziwe, każdy generator pseudolosowy, który głupcy C 0 obwody głębokości D …
1
Lemma i derandomizacja Borela-Cantellego
Czytałem artykuł zatytułowany Losowe wyrocznie z (poza) programowalnością . Ostatni akapit sekcji 2.3 brzmi: [Stosując nasze nowatorskie podejście] nie ma potrzeby stosowania dobrze znanych klasycznych asymptotycznych (i jednolitych) technik derandomizacji opartych na lemacie Borela-Cantellego . Zgodnie z naszą najlepszą wiedzą, podejście to jest nowością w tym dokumencie. Rzuciłem okiem na …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.