Jaka jest najszybciej znana symulacja BPP z wykorzystaniem algorytmów Las Vegas?

$\mathsf{BPP}$ i $\mathsf{ZPP}$ to dwie podstawowe probabilistyczne klasy złożoności.

$\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 maksymalnie $\frac{1}{3}$ (zarówno dla wystąpień TAK, jak i NIE).

Z drugiej strony, algorytmy $\mathsf{ZPP}$ można postrzegać jako te algorytmy probabilistyczne, które nigdy nie zwracają nieprawidłowej odpowiedzi, ilekroć zwracają odpowiedź, jest poprawna. Jednak ich czas działania nie jest ograniczony wielomianem, działają one w oczekiwanym wielomianu.

Niech $\mathsf{ZPTime}(f)$ będzie klasą języka ustaloną przez algorytmy probabilistyczne o zerowym prawdopodobieństwie błędu i oczekiwanym czasie działania $f$ . Są one również określane jako algorytmy Las Vegas i $\mathsf{ZPP} = \mathsf{ZPTime}(n^{O(1)})$ .

Moje pytanie brzmi: jaka jest najlepiej znana symulacja algorytmów $\mathsf{BPP}$ wykorzystaniem algorytmów Las Vegas? Czy możemy je zasymulować w oczekiwanym podwykładniczym czasie? Czy istnieje jakaś poprawa w stosunku do trywialnej symulacji brutalnej siły, która wymaga czasu wykładniczego?

Bardziej formalnie, czy wiemy, czy $\mathsf{BPP} \subseteq \mathsf{ZPTime}(2^{O(n^{\epsilon})})$ czy $\mathsf{BPP} \subseteq \mathsf{ZPTime}(2^{n-n^{\epsilon}})$ dla niektórych $\epsilon>0$ ?

cc.complexity-theory complexity-classes randomness randomized-algorithms echuly
źródło

Co to jest n, długość wejścia? Dlaczego akceptujemy za

2^{n}

$2^n$

domotorp

to to samo, co

2^{p o l y (n) - n^{ϵ}}

$2^{\mathrm{poly}(n)-n^\epsilon}$

2^{p o l y (n)}

$2^{\mathrm{poly}(n)}$

Emil Jeřábek

Uważam to pytanie za dość interesujące. Zredagowałem pytanie, aby uczynić je bardziej czytelnym i precyzyjnym. Możesz edytować dalej. PS: Ja domyślam się, że pewnie chcieli uwzględniać wielomianowo wiele losowych bitów wykorzystywanych przez algorytm BPP jako parametr do czasu symulacji, ale jak zaznacza Emil co napisałaś daje

. Jeśli chcesz, musisz zastąpić BPP określoną klasą algorytmów probabilistycznych z błędem ograniczonym, które mają parametr liczby losowych bitów używanych przez algorytm.

2^{p o l y (n)}

$2^{poly(n)}$

Kaveh

Możesz zapytać, czy możemy symulować algorytm BPP, który wykorzystuje

losowych bitów w

ponieważ symulacja siły brutalnej działa w

czas.

r (n)

$r(n)$

Z P T i m e (2^{r (n) - n^{ϵ}} n^{O (1)})

$\mathsf{ZPTime}(2^{r(n)-n^\epsilon}n^{O(1)})$

2^{r (n)} n^{O (1)}

$2^{r(n)}n^{O(1)}$

Kaveh

Odpowiedzi:

Najpierw zauważyć, że jeżeli dla pewnej stałej , a następnie . (Dowód niedeterministycznej hierarchii czasu.) Zatem udowodnienie takiego włączenia byłoby znaczące, nie tylko dlatego, że jest ulepszoną symulacją, ale także przyniosłoby pierwszy postęp w losowych dolnych granicach czasu od dziesięcioleci. $\mathsf{BPP} \subseteq \mathsf{ZPTIME}[2^{n^{c}}]$ $c$ $\mathsf{BPP} \neq \mathsf{NEXP}$

Następnie rozważyć klasy $\mathsf{PromiseBPP}$ , na której się następujący problem jest " -hard": $\mathsf{PromiseBPP}$

Układ Zbliżanie Prawdopodobieństwo Problem (CAPP) Biorąc pod uwagę układ , wydajność prawdopodobieństwo akceptacja do w czynnik dodatku. $C$ $C$ $1/6$

Wyniki Impagliazzo, Kabanets i Wigderson 2002 sugerują, że algorytm czasu zerowego błędu dla CAPP (gdzie jest rozmiarem ) oznaczałby . W STOC'10 rozszerzyłem to, aby pokazać: zakładając, że dla każdego z bitów wejściowych i rozmiarem , można obliczyć CAPP niedeterministycznie (więc wystarczy błąd zerowy) w $2^{n^{\varepsilon}}$ $n$ $C$ $\mathsf{NEXP} \not\subset \mathsf{P/poly}$ $C$ $k$ $n$ czas, a następnie . Oznacza to, że z pewnością istnieją problemy, które można obliczać z przypadkowością błędu dwustronnego, dla którego algorytmy zerowego błędu, które nawet nieznacznie pokonały wyczerpujące wyszukiwanie, oznaczałyby dolne granice obwodu. Uważam, że należy to interpretować jako możliwą metodę udowodnienia dolnych granic; twój przebieg może się różnić. $2^{k-\omega(\log k)}\mathrm{poly}(n)$ $\mathsf{NEXP} \not\subset \mathsf{P/poly}$

Należy zauważyć, że nawet okazuje jest również otwarty, i udowodnienie , że również oznaczać dolnych granic: w Kabanets i Impagliazzo 2004, jeśli badanie wielomian tożsamość (a problemem) jest w dla wszystkich , wówczas mamy dolne granice dla Stałego lub $\mathsf{RP} \subseteq \mathsf{ZPTIME}[2^{n^{\varepsilon}}]$ $\mathsf{coRP}$ $\mathsf{ZPTIME}[2^{n^{\varepsilon}}]$ $\varepsilon > 0$ $\mathsf{NEXP}$ . Ostatnio (nadchodzące w STOC'13) bezwarunkowo udowodniłem, że albo lub ma obwody o rozmiarze , bazując na metodzie Kabanetów „łatwego świadka”. Oznacza to dwie rzeczy: $\mathsf{BPP} \subseteq \mathsf{ioZPTIME}[2^{n^{\varepsilon}}]/n^{\varepsilon}$ $\mathsf{RTIME}[2^n]$ $n^c$

Jest tak, że dla wszystkich , jest bezwarunkowo - to jest najlepszy bezwarunkowego derandomization z w , które znamy do tej pory. $c$ $\varepsilon > 0$ $\mathsf{RP}$ $\mathsf{ioZPTIME}[2^{n^{\varepsilon}}]/n^c$ $\mathsf{RP/BPP}$ $\mathsf{ZPP}$
Aby rozpocząć uzyskiwanie interesujących symulacji wykładniczych , „tylko” musisz założyć, że nie ma obwodów o stałej wielkości wielomianowej. $\mathsf{BPP}$ $\mathsf{RTIME}[2^n]$

Ryan Williams
źródło

Dzięki Niel za poświęcenie czasu na uczynienie mojej odpowiedzi czytelną :)

Ryan Williams,

Ryan, myślę, że mam zamiar zadać bardzo głupie pytanie, ale proszę bardzo: w pierwszym zdaniu, dlaczego potrzebujesz „dla wszystkich

”? Czy podzbiór BPP ZPTIME (2 ^ (n ^ c)) dla niektórych stałych c nie sugeruje podzbioru BPP RTIME (2 ^ (n ^ c)), a zatem NTIME (2 ^ (n ^ c)), więc BPP jest nie jest równy NEXP lub w inny sposób NTIME (2 ^ (2n ^ c)) jest podzbiorem NTIME (2 ^ (n ^ c))?

ϵ

$\epsilon$

Sasho Nikolov

Wcale nie głupie - w rzeczy samej,

dla niektórych

wystarczy dla

, dziękuję za zwrócenie na to uwagi. Jednak dla innych konsekwencji niezbędne są algorytmy podwykładnicze.

B P P \subseteq N T I M E (2^{n^{c}})

$BPP \subseteq NTIME(2^{n^c})$

c

$c$

B P P \neq N E X P

$BPP \neq NEXP$

Ryan Williams

Ryan: Jeśli chciałbym zrozumieć twój artykuł, z jakimi książkami na temat złożoności obwodów polecasz się zapoznać?

T ....

Cześć Arul, na szczęście Bill Gasarch zadał mi to pytanie i zamieścił następującą stronę z linkami: cs.umd.edu/~gasarch/ryan/ryan.html

Ryan Williams

To zależy od tego, jakie założenia chcesz przyjąć.

W pewnych założeniach twardość, czyli , można uzyskać, że . Oznacza to w szczególności, że , a zatem że każdy język jest akceptowany przez maszynę z Las Vegas (patrz „P = BPP, chyba że E ma obwody subeksponencjalne: Derandomizacja XOR Lemma”, autor: Impagliazzo i Wigderson). $E \not\subseteq SIZE(2^{\varepsilon n})$ $P = BPP$ $BPP = ZPP$ $L \in BPP$

Możesz również przyjąć łagodniejsze założenie twardości, a mianowicie, że , i uzyskać (patrz Lemat 46 w „W poszukiwaniu łatwy świadek: czas wykładniczy a probabilistyczny czas wielomianowy ”(Impagliazzo, Kabanets i Wigderson). $ZPE \not\subseteq \rm{io-DTIME}(2^{\varepsilon n})$ $BPP = ZPP$

Lub Meir
źródło

Pomijając wszelkie postępy w derandomizacji, wydaje mi się, że wymóg, aby maszyna z Las Vegas nie popełniała błędów, jest kluczowy, tak więc losowość w tym przypadku jest niewielka lub żadna.

W przypadku języka BPP ustalonego przez odpowiedni algorytm , który działa na dane wejściowe i ciąg losowy reprezentujący jego losowe wybory, kryterium błędu zerowego implikuje że maszyna z Las Vegas musi upewnić się, który z dwóch przypadków $L$ $A$ $x \in \{0,1\}^n$ $r \in \{0,1\}^{N(n)}$ chwyty. Jeśli podano żadnych dalszych informacji o, to jest zasadniczo problemu obietnica wyrocznia: podany wyroczniąobliczanie, a ze względu na obietnicawydajności jedno wyjściedla co najmniej dwa razy więcej danych wejściowych niż przeciwne wyjście, określ, które wyjście jest bardziej powszechne.

\underset{r}{Pr} (A accepts (x, r)) ⩾ \frac{2}{3} or \underset{r}{Pr} (A accepts (x, r)) ⩽ \frac{1}{3}

$\Pr_r(\text{$A$ accepts $(x,r)$}) \geqslant \tfrac{2}{3} \quad\text{or}\quad \Pr_r(\text{$A$ accepts $(x,r)$}) \leqslant \tfrac{1}{3}$

A

$A$

A^{'}

$A'$

A^{'} (r) = A (x, r)

$A'(r) = A(x,r)$

A^{'}

$A'$

a \in {0, 1}

$a \in \{0,1\}$

1 - a

$1-a$

Chociaż Maszyna do Las Vegas może wykorzystywać losowe techniki, jeśli rzeczywiście jesteśmy zmuszeni traktować jako wyrocznię, możemy zobaczyć, że jedyną dostępną strategią dla maszyny do Las Vegas jest przeprowadzenie dogłębnej (choć nie wyczerpującej) ankiety dotyczącej losowe ciągi , aby zobaczyć, jaka odpowiedź jest podana dla każdego. Można być pewnym tylko, czy znajdzie więcej niż $A'$ $r$ różne ciągi których wszystkie dają ten sam wynik; w przeciwnym razie, z małym (ale niezerowym!) prawdopodobieństwem, może być pecha i uzyskać niereprezentatywną próbkę możliwych wyników. Aby uzyskać błąd zerowy, musi pobrać próbkę co najmniej $2^{N(n)}\!/3$ $r$ wejścia . $2^{N(n)}\!/3$ $r$

Ponieważ maszyna z Las Vegas musi kontrolować przynajmniej stały ułamek wszystkich możliwych losowych ciągów , asymptotycznie nie jesteśmy w lepszej sytuacji niż gdybyśmy testowali deterministycznie wszystkie możliwe ciągi losowe. Nie uzyskujemy żadnej asymptotycznej przewagi w symulacji algorytmów BPP losowo w ustawieniu zerowego błędu, poza tym, co możemy zrobić deterministycznie za pomocą brutalnej siły. $r$

Należy zauważyć, że ten sam argument powoduje rozdzielaniu oracle pomiędzy BPP i ZPP , czyli jest wyrocznią tak, że ponieważ ZPP algorytm bierze wykładniczy czasu podczas BPP algorytm może rozwiązać pytanie wyrocznia w jednym zapytaniu i powodzenie z ograniczonym błędem. Nie mówi jednak nic więcej niż to, co już podejrzewasz (że narzut symulacji może być gorszy niż wielomian) ani że asymptotyki są tak samo złe, jak naiwna deterministyczna symulacja. $A$

{Z P P}^{A} ⫋ {B P P}^{A}

$\mathsf{ZPP}^A \subsetneqq \mathsf{BPP}^A$

Niel de Beaudrap
źródło

popraw mnie, jeśli się mylę: podajesz intuicyjne uzasadnienie, dlaczego derandomizacja wydaje się niemożliwa, ale wiemy, że przy pewnych rozsądnych założeniach BPP, ZPP i P są tym samym. aby intuicja niekoniecznie była dobra

Sasho Nikolov

Ani trochę. Derandomizacja prawdopodobnie byłaby wglądem w to, jak symulować BPP przez P , prawda? Właśnie opisuję, w jaki sposób, jeśli chce bezwarunkowych wyników, które nie wykorzystują struktury samego algorytmu, równie dobrze może przeprowadzić symulację deterministyczną, jak przypadkową z zerowym błędem. Czy może coś jest nie tak z tym wyjaśnieniem?

Niel de Beaudrap

myślę, że wszystko, co mówisz, to to, że naiwna symulacja brutalnej siły BPP przez ZPP nie jest dużo szybsza niż naiwna symulacja brutalnej siły BPP przez P., ale nie widzę, co to ma pokazać. dla mnie jest to tak, jakby ktoś pytał „jaki jest najszybszy algorytm znajdowania maksymalnego dopasowania” i uzyskał odpowiedź „dobrze, nie rozumiejąc struktury dopasowań, to jest czas wykładniczy”. pytanie brzmi, czy istnieje jakiś znany wgląd w strukturę BPP, która umożliwia wydajną symulację ZPP

Sasho Nikolov

@SashoNikolov: Tak naprawdę to nie miał być głęboki wgląd. Z brzmienia pytania wydawało mi się, że jest to granica dla migracji do CS.SE. Postanowiłem odpowiedzieć na to dosłownie, to znaczy: o ile wiemy , najbardziej efektywny oczekiwany czas działania maszyny Las Vegas, która akceptuje język L∈BPP, nie jest dużo lepszy niż maszyna deterministyczna, która bada możliwości brutalnej siły. Odpowiedzi, które mówią, że może być jakaś wielomianowa górna granica, jeśli pewne warunki się utrzymają, są doskonałe i zawierają wiele informacji i głosuję za to; ale odpowiadam na aktualne pytanie.

Niel de Beaudrap,

Myślę, że to ładna odpowiedź (również bardziej czytelna teraz po edycji). Nie mamy wyniku warunkowego, takiego jak „P = ZPP oznacza P = BPP” lub „ZPP = BPP oznacza P = BPP”, więc nadal jest możliwe, że możemy symulować BPP za pomocą algorytmów ZP szybciej niż przy użyciu algorytmów deterministycznych. Jednak wynik relatywizacji wydaje się sugerować, że nie może się to zdarzyć za pomocą symulacji relatywizacyjnej, czy rozumiem poprawnie?

Kaveh