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.
Ostatnie pytanie za pytaniem, czy Huck Bennett PH klasa została zawarta w PP klasy, otrzymał nieco sprzecznych odpowiedzi (wszystko prawda, wydaje się). Z jednej strony podano przeciwnie kilka wyników wyroczni, z drugiej Scott zasugerował, że odpowiedź jest prawdopodobnie pozytywna, ponieważ...
Przypuszcza się, że losowość nie rozszerza potęgi algorytmów wielomianu czasowego, co oznacza, że jest przypuszczalny do utrzymania. Z drugiej strony losowość wydaje się mieć zupełnie inny wpływ na skrócenie czasu wielomianu . Według dobrze znanego wyniku Valiant i Vazirani, redukuje się do poprzez...
Często słyszę, że w przypadku wielu problemów znamy bardzo eleganckie algorytmy randomizowane, ale nie ma, lub tylko bardziej skomplikowane, deterministyczne rozwiązania. Znam jednak tylko kilka przykładów. Najbardziej widoczne Randomized Quicksort (i powiązane algorytmy geometryczne, np. Dla...
Twierdzenie Valiant-Vazirani mówi, że jeśli istnieje wielomianowy algorytm czasu (deterministyczny lub losowy) do rozróżniania między formułą SAT, która ma dokładnie jedno zadowalające przypisanie, a formułą niezadowalającą - wówczas NP = RP . Twierdzenie to zostało udowodnione poprzez wykazanie,...
W jednym zdaniu: czy istnienie hierarchii dla oznaczałoby jakiekolwiek wyniki derandomizacji?BPTIMEbP.T.jaM.mi\mathsf{BPTIME} Powiązane, ale niejasne pytanie brzmi: czy istnienie hierarchii dla implikuje jakieś trudne dolne granice? Czy rozwiązanie tego problemu uderza w znaną barierę w teorii...
Jakie problemy należą do ale nie są znane z ?BPPBPP\mathsf{BPP}PP\mathsf P Mówiąc dokładniej, interesują mnie niezależne problemy, czyli takie, których derandomizacje nie są znane jako równoważne. Na przykład wiadomo, że derandomizacja PIT i wieloczynnikowe wielomianowe rozkładanie na czynniki są...
RP to klasa problemów rozstrzyganych przez niedeterministyczną maszynę Turinga, która kończy się w czasie wielomianowym, ale dopuszczalny jest również błąd jednostronny. P jest zwykłą klasą problemów rozstrzyganych przez deterministyczną maszynę Turinga, która kończy się w czasie wielomianowym. P...
Szukam niezrównoważonych ekspanderów, które są „dobre” i „zajmują mało miejsca”. W szczególności dwustronny wykres lewostronny , , , z lewym stopniem jest rozszerzeniem jeśli dla dowolnego wielkości co najwyżej , liczba różnych sąsiadów w wynosi co najmniej. Wiadomo, że metoda probabilistyczna daje...
Czy istnieje dobra ankieta, która porównuje różne ekstraktory, koncentratory i superkoncentratory i określa najlepsze metody pod względem kompromisu między losowością, czasem i przestrzenią?
W przypadku niektórych algorytmów randomizowanych można go zdemandomizować, usuwając (przy możliwym koszcie w czasie wykonywania) użycie bitów losowych i maksymalizując pewną dolną granicę celu (zwykle obliczaną na podstawie faktu, że twierdzenia dotyczą oczekiwanej wydajności losowej algorytm)....
Chociaż twierdzenie Adlemana pokazuje, że , nie znam żadnej literatury badającej możliwe włączenie . Jakie konsekwencje teoretyczne pod względem złożoności miałoby takie włączenie?BPP⊆P/polyBPP⊆P/poly\mathsf{BPP} \subseteq \mathsf{P}/\text{poly}BQP⊆P/polyBQP⊆P/poly\mathsf{BQP} \subseteq...
Rozważ następujący model: ciąg n-bitowy r = r 1 ... r n jest wybierany równomiernie losowo. Następnie każdy indeks i∈ {1, ..., n} jest umieszczany w zbiorze A z niezależnym prawdopodobieństwem 1/2. Wreszcie, przeciwnik może, dla każdego i∈A osobno, odwrócić r i, jeśli chce. Moje pytanie brzmi: czy...
Niech będzie klasą problemów decyzyjnych mających ograniczony algorytm losowego błędu dwustronnego działający w czasie O ( f ( n ) ) .BPTIME(f(n))BPTIME(f(n))\mathsf{BPTIME}(f(n))O(f(n))O(f(n))O(f(n)) Czy znamy żadnego problemu takie, że P ∈ B P T I M E ( n k ) , ale Q ∉ D T I M E ( n k ) ? Czy...
Interesuje mnie wyraźna funkcja boolowska fa:0 , 1n→0 , 1fa:0,1n→0,1f \colon \\{0,1\\}^n \rightarrow \\{0,1\\}z następującą właściwością: jeśli jest stałe w jakiejś podprzestrzeni afinicznejfafaf , wówczas wymiar tej podprzestrzeni wynosi o ( n ) .0 , 1n0,1n\\{0,1\\}^no ( n )o(n)o(n) Nie jest...
Mówi się, że rozkład ϵ -fooluje funkcję f if | E x ∈ U ( f ( x ) ) - E x ∈ D ( f ( x ) ) | ≤ ϵ . Mówi się, że oszuka klasę funkcji, jeśli oszuka każdą funkcję w tej klasie. Wiadomym jest, że ε -biased obowiązuje oszukać klasę parytetów nad podzbiorów. (patrz...
Znalazłem książkę Pairwise Independence and Derandomization na ten temat, ale jest ona bardziej zorientowana na badania niż na samouczek. Jestem nowy w temacie „Derandomizacji” i dlatego chciałem wiedzieć, od którego odniesienia zacząć? Wolę taki, który omawia literaturę i historię, a także...
Nisan udowodnił w „Psuedorandom Generators for Compound-Bounded Computation”, że istnieje pseudolosowy generator, który „oszuka” obliczenia ograniczone w przestrzeni. Czy ta konstrukcja obowiązuje dla każdej wyroczni (przynajmniej w przypadku zapytań
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”...
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,...
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...