Czytam klasyczny utwór „Twardość kontra losowość” Nisana i Wigdersona. Niech B = { 0 , 1 }b={0,1}B=\{0,1\} , a ustalenie funkcją l : N → Nl:N.→N.l\colon \mathbb{N} \to \mathbb{N} . Określają one rodzinę funkcji G = { Gn: Bl ( n )→ B.n}sol={soln:bl(n)→bn}G = \{G_n : B^{l(n)} \to B^n\} być...
Zakładamy, że . Zatem dobrze znany jest następujący fakt:G∈G(n,p),p=lnn+lnlnn+c(n)nG∈G(n,p),p=lnn+lnlnn+c(n)nG\in G(n,p),p=\frac{\ln n +\ln \ln n +c(n)}{n} Pr[G has a Hamiltonian cycle]=⎧⎩⎨⎪⎪10e−e−c(c(n)→∞)(c(n)→−∞)(c(n)→c)Pr[G has a Hamiltonian...
Interesuje mnie generowanie liczb pseudolosowych do kryptografii. Oprócz rozdziału 5 Menezes / Oorschot / Vanstone ; Rozdział 8 Stinson ; i rozdział 3 Goldreich , gdzie jeszcze mogę znaleźć więcej? Interesują mnie ogólne zasady projektowania PRNG (pożądane właściwości, testy...
W artykule „ Naturalne dowody” Razborova-Rudicha , strona 6, w części, w której dyskutują, że istnieją „silne dowody dolnej granicy na modele obwodów monotonicznych ” i to, jak pasują do zdjęcia, są następujące zdania: Tutaj nie chodzi o konstruktywność - wszystkie właściwości użyte w tych...
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...
Jeśli kulek zostanie rozmieszczonych losowo w koszach równomiernie, w najbardziej obciążonym pojemniku znajdują się kulki z dużym prawdopodobieństwem. W „The Power of Simple Tabulation Hashing” Pătraşcu i Thorup wspominają, że „Chernoff-Hoeffding ogranicza się do aplikacji o ograniczonej...
ppp≤d≤d\le dbias(p)≜|Prx∈{0,1}n(p(x)=0)−Prx∈{0,1}n(p(x)=1)|>ϵbias(p)≜|Prx∈{0,1}n(p(x)=0)−Prx∈{0,1}n(p(x)=1)|>ϵbias(p) \triangleq |\Pr_{x\in\{0,1\}^n}(p(x)=0)-\Pr_{x\in\{0,1\}^n}(p(x)=1)| \gt \epsilon * Gdy piszę losowy wielomian o stopniu ≤d≤d\le d a n zmiennych, można myśleć o każdy...
Niech będzie stałą. Jak możemy w sposób wiarygodny skonstruować pseudolosowy generator, który oszuka -state skończone automaty?dreddredd Tutaj automat skończony -state ma węzły, węzeł początkowy, zestaw węzłów reprezentujących stany akceptacji i dwie skierowane krawędzie oznaczone 0, 1 wychodzące...
Wiadomo, że dodanie randomizacji błędu ograniczonego do PSPACE nie dodaje mocy. Oznacza to, że BPPSAPCE = PSPACE. Nie wiadomo, czy P = BPP, ale wiadomo, że .B P.P.⊆ Σ2)∩ Π2)BPP⊆Σ2∩Π2BPP\subseteq \Sigma_2\cap \Pi_2 Jest zatem możliwe (choć przypuszcza się, że jest to fałsz), że dodanie...
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...
Czy możemy udowodnić ostry wynik koncentracji na sumie niezależnych wykładniczych zmiennych losowych, tj. Niech będą niezależnymi zmiennymi losowymi takimi, że . Niech . Czy możemy udowodnić granice postaci . Wynika to bezpośrednio, jeśli użyjemy formy wariancji granic chernoffa i dlatego uważam,...
Istnieją 4 różne ograniczenia, które możemy mieć, definiując Losowy K-SAT. 1) Całkowita liczba literałów w danych klauzulach to dokładnie K lub AT, w większości K 2) Dany literał może być używany z lub bez zamiany w tej samej klauzuli (A lub A lub A) 3) Daną zmienną można użyć z lub bez zamiany w...
Załóżmy, że jeden ma losowy (BPP) algorytm ZAAA przy użyciu rrr bitów przypadkowości. Istnieją naturalne sposoby na zwiększenie prawdopodobieństwa sukcesu do 1 - δ1−δ1-\delta dla każdego wybranego δ> 0δ>0\delta>0 Niezależne przebiegi + większość głosów: przebieg ZAAA niezależnie T.= Θ (...
Powszechnie wiadomo, że formuły CNF można z grubsza podzielić na 2 szerokie klasy: losowe i strukturalne. Strukturalne formuły CNF, w przeciwieństwie do losowych formuł CNF, wykazują pewien porządek, pokazując wzorce, które prawdopodobnie nie wystąpią przypadkowo. Można jednak znaleźć formuły...
Jaka jest dokładna złożoność czasowa niekierowanego algorytmu przestrzeni logów st-connectivity autorstwa Omer
Opracowałem nową technikę derandomizacji, która ma na celu rekurencyjne algorytmy randomizowane (lub) bardziej ogólnie algorytmy randomizowane, które wykorzystują stos. Niestety nie mogłem znaleźć naturalnych, losowych algorytmów do zastosowania moich technik. Rekurencyjne łańcuchy Markowa i...
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...
Niech klasa BPNC (kombinacja i ) będzie algorytmami równoległymi głębokości dziennika z ograniczonym prawdopodobieństwem błędu i dostępem do losowego źródła (nie jestem pewien, czy to ma inną nazwę). Podobnie zdefiniuj klasę DBPNC, z tym wyjątkiem, że wszystkie procesy mają losowy dostęp do...
Obliczenia niedeterministycznej maszyny Turinga (NTM) są dobrze znane jako drzewa konfiguracji, zakorzenione w konfiguracji początkowej. Każde przejście w programie jest reprezentowane przez łącze ojciec-dziecko w tym drzewie. Podobne drzewa można również skonstruować do wizualizacji obliczeń...
Odwrotne włączenie jest oczywiste, podobnie jak fakt, że każdy samonredukowalny język NP w BPP jest również w RP. Czy znane jest to również w przypadku języków NP