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 też zawsze istniałaby tylko jakaś probabilistyczna maszyna Turinga, dla której prawdopodobieństwa byłyby dobrze określone (lub przynajmniej dolna granica, która powinna być większa niż 1/2)?

Klasa RP jest tutaj względnie arbitralna i można by zadać to pytanie również w przypadku słabszych pojęć losowości (pseudo) niż losowości Kołmogorowa. Ale losowość Kołmogorowa wydaje się dobrym punktem wyjścia.

Zrozumienie słowa „prawdopodobieństwo” byłoby częścią próby wykazania, że losowość Kołmogorowa działa na RP. Pozwólcie jednak, że spróbuję opisać jedno możliwe podejście, wyjaśnić, co to może znaczyć i dlaczego mówiłem o górnej i dolnej granicy:

Niech $s$ będzie (Kołmogorowa losowo) ciąg. Niech $A$ będzie daną probabilistyczną maszyną Turinga odpowiadającą językowi z RP. Uruchom $A$ ze $s$ jako źródłem losowych bitów $n$ razy, kontynuując konsumowanie wcześniej niewykorzystanych bitów od $s$ jeden po drugim.

Dla $p_n^s:=\frac{\text{#YES result in first $n$ runs of $A$ on $s$}}{n}$ $p_+^s:=\limsup_{n\to\infty}p_n^s$ $p_-^s:=\liminf_{n\to\infty}p_n^s$ $p_+^s$ $p_-^s$ $s$ $p_+^s=p_-^s$ $s$ $p_-^{s_1}=p_-^{s_2}$ $s_1$ $s_2$ $p\geq 1/2$ $p\leq p_-^s$ $s$

randomized-algorithms randomness pseudorandomness Thomas Klimpel
źródło

Nie rozumiem pytania. Co rozumiesz przez „<pojęcie losowości> jest wystarczające dla <klasy złożoności>”? RP można zdekandomizować w czasie wielomianowym za pomocą wyroczni dla losowego ciągu Kołmogorowa, jeśli o to pytasz.

Emil Jeřábek

Nie rozumiem, co masz na myśli mówiąc, że RP „zadziała”, i nie rozumiem twojego ostatniego komentarza (maszyny RP zawsze zatrzymują się po wielomianowo wielu krokach, albo z definicji, albo bez utraty ogólności, jeśli używają niewygodnych definicja).

Emil Jeřábek

W samym pytaniu nie rozumiem również, co rozumiesz przez „prawdopodobieństwo”, mówiąc o losowych ciągach Kołomogorowa. W przeciwieństwie do zwykłych „losowych ciągów”, które są pobierane z losowego rozkładu, losowość Kołmogorowa jest faktyczną właściwością „tak” - „nie”, którą dany ciąg ma lub nie ma. Zatem, czy taki ciąg powoduje, że algorytm akceptuje, nie jest zmienną losową i jako taki nie ma sensu pytać o jego prawdopodobieństwo.

Emil Jeřábek

Rozsądnym podejściem jest przyjęcie perspektywy „konstruktywnego Martingalesa” ciągów losowo algorytmicznych. W szczególności można mieć nadzieję, że jeśli nie oszuka , to przełoży się to na „predyktor następnego bitu” dla , a następnie na strategię zakładów pokazującą, że nie jest losowy. Nie wiem, czy to podejście, nawet jeśli , dałoby znaczące współczynniki konwergencji dla i ; jednak najwyraźniej istnieje starsze podejście do badania klas złożoności (słowa kluczowe: „miara ograniczona do zasobów”), które wykorzystuje tę ideę, więc jest trochę nadziei.

s

$s$

A

$A$

s

$s$

s

$s$

p_{+}

$p_+$

p_{-}

$p_-$

Andrew Morgan

Ważne linki z Wikipedii (które zawierają dalsze odniesienia) do mojego poprzedniego komentarza: konstruktywny Martingales (patrz trzecia definicja) i miara ograniczająca zasoby

Andrew Morgan

Odpowiedzi:

Myślę, że pytanie, które tu zadano, jest z grubsza „ czy istnieje sens, w którym możemy zastąpić sekwencję losowych bitów w algorytmie bitami narysowanymi deterministycznie z odpowiednio długiego losowego ciągu Kołmogorowa? ”. To jest przynajmniej pytanie, które spróbuję odpowiedź! (Krótka odpowiedź brzmi „Tak, ale tylko wtedy, gdy najpierw zwiększysz prawdopodobieństwo błędu”)

Tak...

Z pewnością możemy tu coś powiedzieć. Niech będzie jakimś językiem i niech będzie algorytmem, który przyjmuje jako dane wejściowe i ciąg losowy (rozkład równomierny w ) st . Innymi słowy, jest algorytmem, który z prawdopodobieństwem błądzi co najwyżej . $L$ $A$ $x$ $r\in U_{f(|x|)}$ $\{0,1\}^{f(|x|)}$ $\Pr[A(x,r)=L(x)]>1-\epsilon(x)$ $A$ $\epsilon(\cdot)$

Zauważ teraz, że jeśli daje złą odpowiedź na tj. , daje to nam pewne sposoby opisania , w szczególności możemy opisać to jako -ty ciąg, który powoduje błąd naAby to zrobić, po prostu tworzymy maszynę, która ma na stałe zakodowane , , i trochę , i po prostu wylicza opcje z aż znajdzie ty wybór taki, że . $A$ $(x,r)$ $A(x,r)\not=L(x)$ $r$ $i$ $A$ $x.$ $x$ $A$ $i$ $b=1\iff x\in L$ $r'$ $\{0,1\}^{f(|x|)}$ $i$ $r'$ $A(x,r')\not= b$

Teraz, gdy wiemy, że możemy wykorzystać zły wybór losowego ciągu znaków do opisu, zwróćmy uwagę na pewne warunki, które wystarczą, aby zamienić nasz opis na kompresję. Aby opisać , potrzebujemy wystarczającej liczby bitów, aby opisać , , , a następnie kod dla naszej procedury (kod i procedura, którą opisaliśmy), podając jako opis długości $r$ $r$ $x$ $i$ $b$ $A$

| x | + | i | + O (1) = | x | + \log_{2} (2^{f (| x |)} ϵ (x)) + O (1) = | x | + f (| x |) - \log (1 / ϵ (x)) + O (1) .

$|x|+|i|+O(1)=|x|+\log_2(2^{f(|x|)}\epsilon(x))+O(1)=|x|+f(|x|)-\log(1/\epsilon(x))+O(1).$

Przypomnij sobie, że jest długością , więc jest to kompresja if na przykład, gdy . $r$ $f(|x|)$ $r$

\log (1 / ϵ (x)) = | x | + ω (1),

$\log(1/\epsilon(x)) = |x|+\omega(1),$

ϵ (x) = 1 / 2^{2 | x |}

$\epsilon(x)=1/2^{2|x|}$

Na koniec zauważ, że gdyby był losowym ciągiem Kołmogorowa, to nie moglibyśmy mieć takiej kompresji, tak długo, jak prawdopodobieństwo błędu jest wystarczająco małe, losowy ciąg Kołmogorowa zamiast sekwencji losowych bitów spowoduje, że odpowie poprawnie! $r$ $A$ $A$

Zauważ, że jedyną rzeczą, którą wykorzystujemy w jest to, że prawdopodobieństwo błędu jest niewielkie. Nie obchodzi nas, czy ma wyjątkowo długi czas działania, czy ma jeden lub dwustronny błąd. $A$ $A$ $A$

Wracając do pytania o (lub lub ), mówi to, że dopóki zwiększamy prawdopodobieństwo błędu naszych algorytmów, możemy używać losowych ciągów Kołmogorowa zamiast ich losowych bitów. $RP$ $coRP$ $BPP$

... Ale tylko jeśli najpierw wzmocnimy.

Kolejne pytanie może brzmieć „czy mogę to zrobić bez zwiększania prawdopodobieństwa błędu?” Rozważmy następujący algorytm który decyduje i ma prawdopodobieństwo błędu . $A$ $\{0,1\}^*$ $1/2^n$

Na wejściu : $x$

Wygeneruj ciąg $r\in\{0,1\}^n$
Jeśli , odrzuć. $r=x$
Zaakceptować.

Zauważ, że dla każdego wyboru istnieje pewien wybór taki, że błędnie na , a mianowicie wybór który jest , więc nie możemy zastąpić losowej sekwencji bitów używanych przez ciągiem losowym Kołmogorowa bez wzmocnienia to prawdopodobieństwo błędu! $r$ $x$ $A$ $x$ $r$ $x$ $A$

Uwaga na temat źródła: nie jestem pewna, czy którykolwiek z tych tekstów jest nowatorski, ale w piśmie napisałem pierwszy argument do mojego egzaminu kwalifikacyjnego, który ostatecznie będzie dostępny online po zakończeniu przeglądu.

Dylan McKay
źródło

Mój przyjaciel Preetum wskazał na głupotę kodowania maszynę i decydując , kiedy możemy zamiast kodować tylko kawałek, który mówi, czy . Przeredaguję odpowiedź, aby to odzwierciedlić.

M

$M$

M (x)

$M(x)$

x \in L

$x\in L$

Dylan McKay,

Mike Sipser użył podobnego rodzaju argumentu kompresji w swoim fajnym artykule sciencedirect.com/science/article/pii/0022000088900359 (zauważ, że wykresy ekspandera, których potrzebuje, rzeczywiście zostały wyraźnie skonstruowane dl.acm.org/citation.cfm?id=273915 )

Ryan Williams