Przykłady udanej derandomizacji z BPP na P.

15

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?


źródło
2
Wiele algorytmów można zdesandomizować za pomocą ogólnych technik, takich jak metoda warunkowych oczekiwań, metoda pesymistycznych estymatorów i użycie ograniczonych przestrzeni prób niezależności. W rzeczywistości testy pierwotności i testy tożsamości wielomianowej są tak znane, ponieważ są rzadkimi przykładami funkcji naturalnych, które są odporne na standardowe techniki derandomizacji.
Sasho Nikolov
1
@SashoNikolov dziękuję, że komentarz może zostać rozszerzony jako pełna odpowiedź na niektóre przykłady. Czy połączenie twardości z przypadkowością poprzez złożoność obwodów jest jedynym powodem, dla którego ludzie uważają, że ? P=BPP
1
Myślę, że jest to trochę zbyt podstawowe, by odpowiedzieć. Szczegóły i przykłady: patrz rozdział dotyczący derandomizacji w Alon-Spencer: obejmuje on trzy techniki, o których wspomniałem.
Sasho Nikolov
Interesującą rzeczą w klasie BPP jest to, że jej teoretyczna definicja wymaga losowych bitów wejściowych, które można łatwo pokazać, stosując de-randomizację i słabe miary losowości Kołomogrowa, aby nie istniały w domenach skończonych. Nie wiem, jak ludzie mogą żyć z tą niekonsekwencją. Sam nie wierzę, że istnieje wyraźna klasa BPP (jest to NP lub P).

Odpowiedzi:

18

.S.L.=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.S.L.=L.S.S.L.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.

usul
źródło
8
Proszę nie. Odpowiedź jest interesująca.
Emil Jeřábek wspiera Monikę
1
Cześć @Student., Myślę, że ludzie, którzy przyjdą na pytanie zainteresowani przykładami udanej derandomizacji, będą zainteresowani tą odpowiedzią, więc zachowam ją bez znaczenia dla szacunku dla twoich celów (które zostały później edytowane, aby określić złożoność czasu ... )
usul
2
Powinienem również powiedzieć, że pytania i odpowiedzi na tej stronie powinny być sformułowane, aby były ogólnie przydatne dla przyszłych gości jako źródło informacji, a nie tylko dla konkretnych celów plakatu. Dla mnie jedno pytanie bez sztucznych ograniczeń złożoności czasowej i BPP jest o wiele bardziej przydatne.
Emil Jeřábek wspiera Monikę
@ EmilJeřábek Ok dziękuję, że opuścimy post usul tak, jak jest tutaj.
@usul „Chodzi o to, że można myśleć o losowej maszynie Turinga z logami jako o grafie ukierunkowanym o wielkości wielomianowej”. Czy istnieje odpowiednia intuicja, która działa dla NL? Wiem, że L nie jest NL jest przypuszczane, ale PSPACE = NPSPACE, więc przestrzeń może być inna niż czas.
T ....
16

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.

Lance Fortnow
źródło
4
Chociaż zgadzam się z tobą na wysokim poziomie, myślę, że mnogość losowych algorytmów w obliczeniowej teorii grup sugeruje inną ściśle powiązaną klasę interesujących pytań dotyczących derandomizacji, które nie wydają się sprowadzać do PIT. Chociaż większość z nich to funkcje, a nie problemy decyzyjne, niektóre z nich można przekształcić jako interesujące problemy decyzyjne w BPP, np. Cstheory.stackexchange.com/a/11440/129
Joshua
O(fa(n))O(fa(n))bP.P.bP.P.fa(n)P.=bP.P.
12

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).

Raghu Meka
źródło
Jedną z subtelności w P vs BPP, którą chciałbym lepiej zrozumieć, jest różnica między problemami funkcji a problemami decyzyjnymi. Może się zdarzyć, że istnieje wiele problemów funkcyjnych możliwych do rozwiązania (w pewnym sensie) losowo, ale nie deterministycznie w czasie wielomianowym, a jednak P = BPP. Wygląda na to, że twoje przykłady prawdopodobnie łatwo przekładają się na problemy decyzyjne, prawda?
usul
1
Problemy decyzyjne i funkcyjne są nieco bardziej subtelne niż w świecie NP, ale wciąż wiele wiadomo: na przykład ten artykuł w sekcji 3 podaje przykład „losowego problemu wyszukiwania rozwiązanego w czasie wielokrotnym”, którego nawet nie można rozstrzygnąć. Ale jeśli funkcja jest jeden do jednego, to P = BPP implikuje, że „losowy problem funkcji rozwiązanej w czasie wielokrotnym” ma deterministyczny algorytm czasu wielokrotnego (w artykule podano również wiele innych przykładów)
Joe Bebel