Pytania otagowane jako randomized-algorithms

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

4
Czy możemy szybko wygenerować idealnie jednolicie mod 3 lub rozwiązać problem NP?
Szczerze mówiąc, nie wiem zbyt wiele o tym, jak generowana jest liczba losowa (komentarze są mile widziane!), Ale załóżmy następujący model teoretyczny: Możemy uzyskać liczby całkowite jednolicie losowe z a naszym celem jest wyprowadza liczbę całkowitą jednolicie losową z [1,3].[ 1 , 2 n ][1,2n][1,2^n] Oto proste rozwiązanie, którego oczekiwany …
1
Losowa hierarchia wielomianowa?
Zastanawiam się, co by się stało, gdyby w definicji (wielomianowa hierarchia, patrz np. Tutaj ) rola zostałaby zastąpiona przez ?PHPHPHNPNPNPRPRPRP Wydaje się, że można jeszcze zbudować hierarchię, tak samo jak jest zbudowany, tylko za pomocą wszędzie zamiast i zamiast . Nazwijmy to Randomized Polynomial Hierarchy ( ).PHPHPHRPRPRPNPNPNPcoRPcoRPcoRPcoNPcoNPcoNPRPHRPHRPH Moje pierwsze przypuszczenie …
5
Lista algorytmów inspirowanych kwantem
Postępy w dziedzinie obliczeń kwantowych doprowadziły do ​​opracowania nowych klasycznych algorytmów. Godne uwagi ostatnie przykłady to inspirowane kwantem algorytmy algebry liniowej: Klasyczny algorytm inspirowany kwantem dla systemów rekomendacji Klasyczne algorytmy inspirowane kwantem do analizy głównych komponentów i nadzorowanego grupowania Inspirowana kwantem regresja stochastyczna niskiej rangi z logarytmiczną zależnością od wymiaru …
2
Dolna granica szacowania dla
Chciałbym wiedzieć (związany z tym drugim pytaniem ), czy dolne granice były znane z następującego problemu testowego: jeden ma dostęp do zapytania do sekwencji liczb nieujemnych i , z obietnicą, że albo lub .an≥⋯≥a1an≥⋯≥a1a_n \geq \dots\geq a_1ε∈(0,1)ε∈(0,1)\varepsilon \in (0,1)∑nk=1ak=1∑k=1nak=1\sum_{k=1}^n a_k = 1∑nk=1ak≤1−ε∑k=1nak≤1−ε\sum_{k=1}^n a_k \leq 1-\varepsilon Ile zapytań (wyszukiwań) jest wystarczających …
1
Znajdź przybliżony argmax, używając tylko przybliżonych maksymalnych zapytań
Rozważ następujący problem. nnnv1,⋯,vn∈Rv1,⋯,vn∈Rv_1, \cdots, v_n \in \mathbb{R}S⊆{1,⋯,n}S⊆{1,⋯,n}S \subseteq \{1,\cdots,n\}maxi∈Svimaxi∈Svi\max_{i \in S} v_i Ten problem jest prosty: możemy użyć wyszukiwania binarnego, aby znaleźć argmax z zapytaniami . tj. Zbuduj kompletne drzewo binarne z liści odpowiadających indeksom. Zacznij od korzenia i zejdź do liścia w następujący sposób. W każdym węźle zapytaj …
1
Klasy złożoności losowości i małych obwodów
Niech będzie klasą złożoności, a będzie losowym odpowiednikiem zdefiniowanego jako w odniesieniu do . Bardziej formalnie podajemy wielomianowo wiele bitów losowych i akceptujemy dane wejściowe, jeśli prawdopodobieństwo akceptacji jest większe niż .Cdo\mathcal{C}BP-CBPdo\textrm{BP-}\mathcal{C}Cdo\mathcal{C}BPPBPP\textrm{BPP}PP.\textrm{P}232)3)\frac{2}{3} Wiadomo, że dla klasy obwodów nierównomiernych mamy :BPAC0= AC0BPAC0=AC0\textrm{BPAC}^0=\textrm{AC}^0 Miklós Ajtai, Michael Ben-Or: Twierdzenie o probabilistycznych obliczeniach stałej …
1
Czy prawdziwą losowość (możliwe do udowodnienia) można zastąpić losowością Kołmogorowa dla RP?
Czy były jakieś próby wykazania, że losowość Kołmogorowa byłaby wystarczająca dla RP ? Czy prawdopodobieństwo użyte w stwierdzeniu „Jeśli prawidłowa odpowiedź brzmi TAK, to wówczas (probabilistyczna maszyna Turinga) zwraca TAK z prawdopodobieństwem ...” zawsze byłoby dobrze zdefiniowane w takim przypadku? Czy byłyby tylko górne i dolne granice tego prawdopodobieństwa? Czy …
1
Przykłady zastosowania estymatorów stronniczych
Biodrowe estymatory są przydatne w statystykach, ponieważ mogą bardziej zoptymalizować błąd średniokwadratowy niż ten, którym może zarządzać bezstronny estymator . Zastanawiałem się, czy teoretycznie CS, czy istnieją jakieś bardzo godne uwagi przykłady skutecznego wykorzystania stronniczych estymatorów. Zdaję sobie sprawę, że ta lista może być długa i jeśli tak, mogę zmodyfikować …
1
Kiedy BPP z tendencyjną monetą równa się standardowemu BPP?
Pozwól probabilistycznej maszynie Turinga mieć dostęp do nieuczciwej monety, która pojawia się z prawdopodobieństwem (trzepnięcia są niezależne). Zdefiniuj jako klasę języków rozpoznawalnych przez taki komputer w czasie wielomianowym. Standardowym ćwiczeniem jest wykazanie, że:B P P ppppBPPpBPPpBPP_p A) Jeśli jest racjonalne lub nawet obliczalne z to . (Przy -computable to znaczy: …
2
Dokładna formuła dla liczby drzew rozpinających prostokąta
Ten blog mówi o generowaniu „krętych małych labiryntów” za pomocą komputera i ich liczeniu. Wyliczenia można dokonać za pomocą algorytmu Wilsona, aby uzyskać UST , ale nie pamiętam wzoru na ich liczbę. http://strangelyconsistent.org/blog/youre-in-a-space-of-twisty-little-mazes-all-alike Zasadniczo Twierdzenie o Drzewie Matrycowym stwierdza, że ​​liczba drzew spinających na wykresie jest równa wyznacznikowi macierzy Laplaciana …
2
Jakie jest minimum we wszystkich rozkładach wektorów jednostkowych wariancji iloczynu wektorów?
Usiłuję znaleźć rozkład na losowych wektorów, powiedzmy , na sferze jednowymiarowej (gdzie ), która minimalizuje zastrzeżeniem ograniczenia \ mathbb {E} [x_i ^ Tx_j] = 0 .nnnx1,…,xnx1,…,xnx_1,\ldots, x_nkkkn>kn>kn > kmaxi≠jVar(xTixj)maxi≠jVar(xiTxj)\max_{i\neq j} \mathrm{Var}(x_i^T x_j)E[xTixj]=0E[xiTxj]=0\mathbb{E}[x_i^Tx_j]=0 Próbowałem niektórych dystrybucji i prawie wszystkie mają wariancję . Na przykład zarówno rozkład, w którym każda współrzędna każdego …
2
Odwrotność do nierówności Fano?
Nierówność Fano można wyrazić w wielu formach, a jedna szczególnie przydatna wynika (z niewielką modyfikacją) Oded Regev : Niech XXX będzie zmienną losową, a Y=g(X)Y=g(X)Y = g(X) gdzie g(⋅)g(⋅)g(\cdot) jest procesem losowym. Załóżmy, że istnieje procedura fff która dla y=g(x)y=g(x)y = g(x) może zrekonstruować xxx z prawdopodobieństwem ppp . Następnie …
1
Jaka jest zaleta projektowania deterministycznych algorytmów rozproszonych?
Algorytmy rozproszone odporne na awarie mogą być deterministyczne lub probabilistyczne. Weźmy na przykład problem konsensusu. Paxos jest deterministyczny w tym sensie, że biorąc pod uwagę przyjęte założenie, zawsze działa. Natomiast randomizowany konsensus działa z określonym prawdopodobieństwem. Jaka jest zaleta projektowania i stosowania algorytmu deterministycznego? Założenia, na których opierają się algorytmy …
3
Jaka jest najszybciej znana symulacja BPP z wykorzystaniem algorytmów Las Vegas?
BPPBPP\mathsf{BPP} iZ P PZPP\mathsf{ZPP} to dwie podstawowe probabilistyczne klasy złożoności. B P PBPP\mathsf{BPP} jest klasą języków ustaloną przez probabilistyczne algorytmy Turinga w czasie wielomianowym, w których prawdopodobieństwo zwrotu nieprawidłowej odpowiedzi przez algorytm jest ograniczone, tzn. Prawdopodobieństwo błędu wynosi maksymalnie13)13\frac{1}{3} (zarówno dla wystąpień TAK, jak i NIE). Z drugiej strony, algorytmy …
1
Jakie są wyniki algorytmów szacujących wielomiany dla danego zestawu punktów?
Wydaje się, że istnieje wiele randomizowanych algorytmów do testowania tożsamości wielomianowej, sprawdzających, czy dany wielomian ma wartość zero. Czy są jakieś wyniki algorytmów, które dokonują pewnego rodzaju oszacowania wielomianów w określonym zestawie punktów? Może to być na przykład przybliżenie, dla jakiej części tych punktów wielomian ocenia się na zero, lub …
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.