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=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 mamy do derandomizacji (znowu nie połączenie twardości czy wyroczni)?

Zachowaj przykłady tylko tam, gdzie wykazano poprawę złożoności czasowej od losowego poli do deterministycznego poli lub czegoś, co jest bardzo bliskie konkretnym problemom.

Poniżej znajduje się bardziej komentarz i nie wiem wiele, pomoże to zapytanie.

Chazelle ma bardzo intrygujące stwierdzenie w http://www.cs.princeton.edu/~chazelle/linernotes.html w części „The Discrepancy Method: Randomness and Complexity (Cambridge University Press, 2000)”.

„To dla mnie niekończące się źródło fascynacji, że głębsze zrozumienie obliczeń deterministycznych powinno wymagać opanowania losowości. Napisałem tę książkę, aby zilustrować to potężne połączenie. Od minimalnych drzew opinających do programowania liniowego po triangulacje Delaunaya, najbardziej wydajnymi algorytmami są często derandomizacje rozwiązań probabilistycznych. Metoda rozbieżności rzuca światło na jedno z najbardziej owocnych pytań w całej informatyce: jeśli uważasz, że potrzebujesz losowych bitów, powiedz nam dlaczego?

.$SL = L$

oznacza randomizowane logspace i R L = L jest mniejsze wersja problemu R P = P . Główny krok, to dowód Reingold w '04 ( „nieukierunkowane ST połączeń w logspace”), które S L = L , gdzie S oznacza „symetryczny” i S L jest klasa pośrednia pomiędzy R L i L .$RL$$RL=L$$RP=P$$SL = L$$S$$SL$$RL$$L$

Chodzi o to, że można myśleć o losowej maszynie Turinga z logami jako grafie ukierunkowanym o wielomianach, gdzie węzły to stany maszyny, a algorytm RL wykonuje losowy spacer o dobrych właściwościach. SL odpowiada niekierowanym grafom tego formularza. Dowód Reingolda oparty na pracy na grafach ekspanderów, w szczególności „zygzakowatym produkcie” Reingolda, Vadhana i Wigdersona, aby wykonać dowolny losowy spacer na niekierowanym grafie z dobrymi właściwościami i przekształcić go w zwykły spacer zachowujący te właściwości.

edytuj to pytanie zostało opublikowane, zanim pytanie zostało wyraźnie zmienione, aby skupić się wyłącznie na P vs BPP ... Zostawiam to, ponieważ wydaje się interesujące.

Zasadniczo istnieje tylko jeden interesujący problem w BPP, o którym nie wiadomo, że jest w P: testowanie tożsamości wielomianowej, biorąc pod uwagę, że obwód algebraiczny jest wielomianem, który generuje identycznie zero. Impagliazzo i Kabanets pokazują, że PIT w P implikuje pewne dolne granice obwodu. Więc dolne granice obwodu są jedynym powodem (ale całkiem dobrym), że naszym zdaniem P = BPP.

Oprócz testowania tożsamości wielomianowej jednym innym bardzo ważnym problemem, o którym wiadomo, że jest w BPP, ale nie w P, jest przybliżenie stałej macierzy nieujemnej lub nawet liczby idealnych dopasowań na wykresie. Istnieje randomizowany algorytm wieloczasowy do przybliżania tych liczb w ramach współczynnika (1 + eps), podczas gdy najlepsze algorytmy deterministyczne osiągają jedynie przybliżone współczynniki ~ 2 ^ n.

Chociaż stały jest głównym przykładem, istnieje wiele przybliżonych problemów z liczeniem, dla których istnieje ogromna luka między algorytmami losowymi (zwykle opartymi na metodach „MCMC”) a deterministycznymi algorytmami.

Innym problemem w podobnym stylu jest przybliżenie objętości wyraźnie podanego ciała wypukłego (powiedzmy wielościan opisany przez zbiór nierówności liniowych).