Pytania otagowane jako randomized-algorithms

Algorytm, którego zachowanie jest determinowane przez jego dane wejściowe, oraz generator generujący jednolicie losowe liczby.

3
W jakiej klasie są algorytmy losowe, które mają błąd z dokładnie 25% szansą?
Załóżmy, że rozważam następujący wariant BPP, który pozwala nam nazywać się E (xact) BPP: Język jest w EBPP, jeśli istnieje wielomianowy losowy czas TG, który akceptuje każde słowo z prawdopodobieństwem dokładnie 3/4 i każde słowo nie w język z prawdopodobieństwem dokładnie 1/4. Oczywiście EBPP jest zawarty w BPP, ale czy …
1
Złożoność próbkowania (w przybliżeniu) transformaty Fouriera funkcji boolowskiej
Jedną rzeczą, którą komputery kwantowe mogą zrobić (być może nawet z tylko BPP + obwody kwantowe głębokości logarytmicznej), jest przybliżenie próbki transformaty Fouriera funkcji logicznej wartościowej w P.±1±1\pm 1 Tutaj i poniżej, kiedy mówię o próbkowaniu transformaty Fouriera, mam na myśli wybranie x zgodnie z . (Znormalizowane w razie potrzeby …
2
Czy w praktyce wykorzystywane są teoretycznie generatory pseudolosowe?
O ile mi wiadomo, większość implementacji generowania liczb pseudolosowych w praktyce wykorzystuje metody, takie jak rejestry sprzężenia zwrotnego z przesunięciem liniowym (LSFR) lub te algorytmy „Mersenne Twister”. Chociaż zdają wiele (heurystycznych) testów statystycznych, nie ma teoretycznych gwarancji, że wyglądają pseudolosowo, powiedzmy, na wszystkie skutecznie obliczalne testy statystyczne. Jednak metody te …
3
Randomize or Not?
To pytanie jest inspirowane koszulką Georgia Tech Al Algorytmy i Randomness Center , która pyta „Randomize or not ?!” Istnieje wiele przykładów, w których randomizacja pomaga, szczególnie podczas działania w środowiskach przeciwnych. Istnieją również ustawienia, w których losowanie nie pomaga ani nie boli. Moje pytanie brzmi: Jakie są ustawienia, kiedy …
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 …
2
Które algorytmy randomizowane mają wykładniczo małe prawdopodobieństwo błędu?
Załóżmy, że algorytm losowy używa rrr losowych bitów. Najniższe prawdopodobieństwo błędu, jakiego można się spodziewać (nie spełniając deterministycznego algorytmu z błędem 0), wynosi 2)- Ω ( r )2)-Ω(r)2^{-\Omega(r)} . Które algorytmy losowe osiągają tak minimalne prawdopodobieństwo błędu? Oto kilka przykładów, które przychodzą na myśl: Algorytmy próbkowania, np. Gdzie chcemy oszacować …
1
Naturalne twierdzenia udowodnione tylko „z dużym prawdopodobieństwem”?
Istnieje wiele sytuacji, w których zrandomizowany „dowód” jest znacznie łatwiejszy niż dowód deterministyczny, którego kanonicznym przykładem jest testowanie tożsamości wielomianowej. Pytanie : Czy istnieją jakieś naturalne „twierdzenia” matematyczne, w których znany jest dowód losowy, ale dowód deterministyczny nie? Przez „losowy dowód” stwierdzenia rozumiem toPPP Istnieje algorytm randomizowany, który przyjmuje dane …
1
Czy wystarczy, aby ograniczenia programu liniowego były spełnione w oczekiwaniu?
W artykule Randomized Primal-Dual analiza RANKING dla Online Dwustronnego dopasowywania , udowadniając jednocześnie, że algorytm RANKING jest -konkurencyjne, autorzy pokazują, że dualność jest wykonalna w oczekiwaniu (patrz Lemat 3 na stronie 5). Moje pytanie brzmi:(1−1e)(1−1e)\left(1 - \frac{1}{e}\right) Czy wystarczy, aby ograniczenia programu liniowego były spełnione w oczekiwaniu? Jedną rzeczą jest …
1
Ponowne użycie 5 niezależnych funkcji skrótu do sondowania liniowego
W tablicach skrótów, które rozwiązują kolizje za pomocą sondowania liniowego, w celu zapewnienia oczekiwanej wydajności , zarówno konieczne, jak i wystarczające jest, aby funkcja skrótu pochodziła z 5-niezależnej rodziny. (Wystarczalność: „Sondowanie liniowe ze stałą niezależnością”, Pagh i in. , Konieczność: „O k-niezależności wymaganej przez sondowanie liniowe i niezależność minutową”, Pătraşcu …
1
Generowanie wykresów za pomocą trywialnych automorfizmów
Sprawdzam jakiś model kryptograficzny. Aby pokazać jego nieadekwatność, opracowałem wymyślony protokół oparty na izomorfizmie grafowym. Zakładanie istnienia algorytmów BPP zdolnych do generowania „trudnych wystąpień problemu z izomorfizmem grafów” jest „powszechne” (a jednak kontrowersyjne!). (Wraz ze świadkiem izomorfizmu). W moim skonstruowanym protokole założę istnienie takich algorytmów BPP, które spełniają jeden dodatkowy …
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) …
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.