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: $p$ $BPP_p$

A) Jeśli jest racjonalne lub nawet obliczalne z to . (Przy -computable to znaczy: jest losowo wielomianowej algorytm, który jest podawany w pojedynczych, powraca whp binarna racjonalnymi mianowniku , który znajduje się w odległości w ). $p$ $BPP$ $BPP_p=BPP$ $BPP$ $n$ $2^n$ $2^{-n-1}$ $p$

B) Dla niektórych nieobliczalnych klasa zawiera nierozstrzygalny język, a zatem jest większa niż . Takie wartości tworzą gęsty zbiór w . $p$ $BPP_p$ $BPP$ $p$ $(0,1)$

Moje pytanie brzmi: co dzieje się pomiędzy? Czy istnieje kryterium dla ? W szczególności: $BPP_p=BPP$

1) Czy istnieją prawdopodobieństwa , tak że ? (Mogą być obliczalne w niektórych wyższych klasach). $BPP$ $p$ $BPP_p=BPP$

2) Czy szerszy niż dla wszystkich nieobliczalnych ? (Parametry, o których mowa, to parametry, których rozwinięcie binarne zawiera bardzo długie sekwencje zer i / lub jedynek. W takim przypadku obliczanie bitów przez losowe próbkowanie może zająć bardzo długi, a nawet nieobliczalny czas, a problemu nie można przeskalować do czasu wielomianowego. Czasami trudność można pokonać przez inną bazę ekspansji, ale niektóre mogą oszukać wszystkie bazy). $BPP_p$ $BPP$ $p$ $p$

cc.complexity-theory randomized-algorithms probabilistic-complexity Daniil Musatov
źródło

Co dokładnie masz na myśli mówiąc, że p jest (nie) obliczalny?

daniello,

Dodałem definicję

computable. Aby obliczyć w ogóle, można po prostu porzucić słowa „losowy wielomian” lub po prostu powiedzieć, że rozszerzenie binarne jest obliczalne. (Przy ograniczonych zasobach to nie to samo.)

B P P

$BPP$

Daniil Musatov

Myślę, że

dla każdego nieobliczalnego

ponieważ biorąc pod uwagę monetę niezależną od

można obliczyć

-ty kawałek

przez próbkowanie. Załóżmy, że możemy obliczyć

-ty bit w czasie

, wówczas język, który zawiera

dla wszystkich

tak że

'bit

wynosi

jest w

B P P_{p} \neq B P P

$BPP_p \neq BPP$

p

$p$

p

$p$

n

$n$

p

$p$

n

$n$

f (n)

$f(n)$

1^{x}

$1^x$

x

$x$

f^{- 1} (x)

$f^{-1}(x)$

p

$p$

1

$1$

B P P_{p}

$BPP_p$ , ale najwyraźniej jest to niemożliwe do obliczenia.

daniello,

Jest to z pewnością prawda dla zdecydowanej większości nieobliczalnych

. Jest jednak zastrzeżenie: jeśli

zawiera bardzo długie sekwencje zer i jedynek, może wymagać bardzo długiego próbkowania, aby ustalić

-ty bit. To próbkowanie może być tak długie, że

byłoby niemożliwe do obliczenia (podobnie jak funkcja Busy Beavers). Wątpię również, aby można było to dokładnie obliczyć z samego próbkowania. I wydaje się, że bez obliczenia

nie można rozpoznać wspomnianego języka.

p

$p$

p

$p$

n

$n$

f (n)

$f(n)$

f (n)

$f(n)$

Daniil Musatov,

Odpowiedzi:

1) Tak, ale tylko z powodu twojej definicji. Weź jednoargumentowy język (tak, wiem, że to może być puste, w takim przypadku po prostu weź coś jeszcze większego niż ), co jest bardzo rzadkie w tym sensie, że jeśli nie jest to wieża , czyli w postaci . Zdefiniuj . To nie jest $L\in EXP\setminus BPP$ $EXP$ $n\notin L$ $n$ $2's$ $2^{2^{2^\ldots}}$ $p=\sum_{n\in L} 1/n$ $p$ obliczalne, ale może być aproksymowane w do wystarczająco małego błędu addytywnego, który pozwala na symulację maszyny . $BPP$ $p$ $P$ $BPP_p$

Gdybyś zdefiniowane -computable takie, że chcesz przybliżonej do addytywnej błędu (zamiast ) w czasie wielomianowym, sytuacja byłaby inna. $BPP$ $p$ $1/n$ $1/2^n$

Aktualizacja. Poniższa odpowiedź dotyczy przypadku, w którym dopuszczalny błąd addytywny wynosi zamiast . $2^{-n}$ $2^{-n-1}$

2) Tak, ponieważ tutaj możesz zapomnieć o wielomianowym ograniczeniu klas i próbkując razy, możesz uzyskać ty bit w . $2^n$ $n$ $p$ $BPP_p$

domotorp
źródło

2) Myślę, że centralne twierdzenie graniczne sugeruje, że należy spróbować

, a nie

, czasy nabyć

precyzji. Ale głównym problemem jest to, że czasami potrzebujemy znacznie większej precyzji. Powiedz, jeśli

2^{2 n}

$2^{2n}$

2^{n}

$2^n$

2^{- n}

$2^{-n}$

wtedy trzeba

| p - \frac{1}{2} | < ϵ

$|p-\frac12|<\epsilon$

próbki do obliczenia nawet pierwszej cyfry. A potrzebna liczba próbek może być dowolnie, a nawet nieobliczalna, duża. Punkt jest nieco wyjaśniony w edycji.

\frac{1}{ϵ^{2}}

$\frac1{\epsilon^2}$

Daniil Musatov,

@Daniil: Jak również skomentowałem to pytanie, nie poprosiłeś o obliczenie cyfr w swojej definicji

computable. Tak więc, jeśli

jest równe, powiedzmy,

, to należy zgadywać

dla pierwszej cyfry po przecinku zgodnie z def.

B P P

$BPP$

p

$p$

0.01111111111

$0.01111111111$

1

$1$

domotorp

Mówimy teraz o nieobliczalnym

, prawda? Jeśli dobrze rozumiem, sugerujesz nie obliczać, próbkując cyfry

, ale zamiast tego obliczyć, czy

-ta cyfra

binarnego racjonalnego przybliżenia

wynosi 1. Ale tutaj mamy ten sam problem: obliczyć pierwszą cyfrę, aby rozróżnić 0,010000000001 i 0,001111111110.

p

$p$

p

$p$

i

$i$

2^{- i - 1}

$2^{-i-1}$

p

$p$

Daniil Musatov,

@Daniil: OK, mój zły, myślałem, że chcesz binarnego racjonalnego, którego odległość wynosi co najwyżej

. Zaktualizowałem odpowiednio swoją odpowiedź. Czy jesteś zadowolony z mojego rozwiązania 1)?

2^{- n}

$2^{-n}$

p

$p$

domotorp