Pytania oznaczone «randomized-algorithms»

Dowód Adlemana, że jest zawarty w pokazuje, że jeśli istnieje algorytm losowy dla problemu, który działa w czasie na wejściach o rozmiarze , to istnieje również algorytm deterministyczny dla problemu, który działa w czasie na materiale o wielkości [algorytm prowadzi randomizowane algorytm na...

Wielu wierzy, że . Jednak wiemy tylko, że B P P znajduje się na drugim poziomie hierarchii wielomianowej, tj. B P P ⊆ Σ P 2 ∩ Π P 2 . Etap kierunku pokazano B P P = P jest najpierw doprowadzić go do pierwszego poziomu hierarchii, to znaczy wielomian B P P ⊆ N P .BPP=P⊆NPBPP=P⊆NP\mathsf{BPP} =...

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

Czy istnieje interesujący przykład losowego algorytmu dla problemu wyszukiwania, który zawsze generuje tę samą (poprawną) odpowiedź, niezależnie od wewnętrznej losowości, ale który wykorzystuje losowość, dzięki czemu jej oczekiwany czas działania jest lepszy niż czas działania najszybszego znanego...

Logarytmiczna jednolita NC jest zawarta w deterministycznej przestrzeni polilogu (czasami zapisywanej jako PolyL). Czy RNC o jednolitej przestrzeni logów również należy do tej klasy? Standardowa losowa wersja PolyL powinna być w PolyL, ale nie widzę, aby (jednolity) RNC był w randomizowanym-PolyL....

Właśnie nauczyłem losowego algorytmu skrótu Karger-Stein w mojej klasie algorytmów dla absolwentów. To prawdziwy klejnot algorytmiczny , więc nie mogę tego nie uczyć, ale zawsze denerwuje mnie, ponieważ nie znam innych zastosowań głównej techniki. (Trudno więc przypisać pracę domową, która...

Edycja: wybieram odpowiedź z najwyższym wynikiem do 6 grudnia 2012 r. To delikatne pytanie. Pojęcie (deterministycznych) algorytmów sięga BC. Co z algorytmami probabilistycznymi? W tym wpisie wiki algorytm Rabina dla problemu najbliższej pary w geometrii obliczeniowej podano jako pierwszy...

Jestem pewien, że wszyscy wiedzą o eksperymencie igły Buffona w XVIII wieku, który jest jednym z pierwszych algorytmów probabilistycznych do obliczeniaππ\pi. Implementacja algorytmu w komputerach zwykle wymaga użycia ππ\pilub funkcja trygonometryczna, która nawet jeśli są zaimplementowane jako...

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

Ważny artykuł z 2003 roku autorstwa Childsa i in.wprowadził „problem drzew połączonych”: problem dopuszczający wykładnicze przyspieszenie kwantowe, który nie jest podobny do żadnego innego znanego nam problemu. W tym problemie otrzymaliśmy wykładniczo duży wykres, taki jak ten pokazany poniżej,...

Słynny Yao Minimax Zasada stwierdza zależność między złożonością i dystrybucyjnej randomizowanym złożoności. Niech PPP być problemu ze skończonego zbioru wejść i skończonego zbioru deterministycznego algorytmu rozwiązania . Niech także oznacza rozkład wejściowy, a niech oznacza rozkład...

W przypadku algorytmów losowych przyjmujących rzeczywiste wartości „sztuczka medianowa” jest prostym sposobem zmniejszenia prawdopodobieństwa niepowodzenia do dowolnego progu , kosztem tylko wielokrotności narzut. Mianowicie, jeśli wyjście mieści się w „dobrym zakresie” z prawdopodobieństwem (co...

Kiedy uczę ograniczeń ogona, używam zwykłego postępu: Jeśli twoje Rv jest dodatnie, możesz zastosować nierówność Markowa Jeśli masz niezależność, a także ograniczoną wariancję, możesz zastosować nierówność Czebyszewa Jeśli każdy niezależny rv ma również ograniczone wszystkie chwile, możesz użyć...

Jeśli jest funkcją wypukłą, to nierówność Jensena stwierdza, że i mutatis mutandis, gdy jest wklęsłe. Oczywiście w najgorszym przypadku nie można górnej granicy w kategoriach dla wypukłego , ale czy istnieje granica, która idzie w tym kierunku, jeśli jest wypukły, ale „niezbyt wypukły”? Czy...

Niech f:{0,1}n→(2−n,1]f:{0,1}n→(2−n,1]f \colon \lbrace 0,1 \rbrace ^ n \to (2^{-n},1] będzie funkcją. Chcemy oszacować średnią fff ; to znaczy: E[f(n)]=2−n∑x∈{0,1}nf(x)E[f(n)]=2−n∑x∈{0,1}nf(x)\mathbb{E}[f(n)]=2^{-n}\sum_{x\in \lbrace 0,1 \rbrace ^ n}f(x) . NOTE: In the OP, the range of f was...

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

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

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

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