Problemy w P z znacznie szybszymi algorytmami randomizowanymi

Czy są jakieś problemy w które mają algorytmy losowe przekraczające dolne granice algorytmów deterministycznych? Mówiąc konkretniej, czy znamy jakieś dla którego ? Tutaj oznacza zestaw języków rozstrzygalnych przez losową TM z błędem o stałym ograniczeniu (jedno- lub dwustronny) w krokach . $\mathsf{P}$ $k$ $\mathsf{DTIME}(n^k) \subsetneq \mathsf{PTIME}(n^k)$ $\mathsf{PTIME}(f(n))$ $f(n)$

Czy losowość kupuje nam coś w $\mathsf{P}$ ?

Dla jasności szukam czegoś, w którym różnica jest asymptotyczna (najlepiej wielomianowa, ale zadowoliłbym się polilogarytmią), a nie tylko stałą.

Poszukuję algorytmów asymptotycznie lepszych w najgorszym przypadku. Algorytmy o lepszej oczekiwanej złożoności nie są tym, czego szukam. Mam na myśli algorytmy losowe jak w RP lub BPP, a nie ZPP.

algorithms complexity-theory randomized-algorithms

— aelguindy
źródło

Może „Technika Yao” jest tym, czego szukasz. Krótki opis można znaleźć na stronie cs.pitt.edu/~kirk/cs2150/yao/yao.html

— Wu Yin,

@WuYin, jeśli dobrze rozumiem, że idzie to w kierunku algorytmów randomizowanych o niższych granicach przez średnie zachowanie algorytmu deterministycznego w analizie przypadków. Przyjrzę się temu, ale sposób, w jaki go widzę, może tylko doprowadzić do udowodnienia tej losowości nic nam nie kupuje w

P

$P$ .. Czy mam rację?

— aelguindy

Aby znaleźć dowolny element w sekwencji o długości

n

$n$ z rangą w [

\frac{n}{4}

$\frac{n}{4}$ ,

\frac{3 * n}{4}

$\frac{3*n}{4}$ ], możemy po prostu zwrócić dowolny losowy element i będzie to poprawne z

\frac{1}{2}

$\frac{1}{2}$ prawdopodobieństwo stąd jego O (1)! Podczas gdy algorytm deterministyczny zbadałby przynajmniej ułamek danych wejściowych i stąd

Ω (n)

$\Omega(n)$ .

— rizwanhudda

@rizwanhudda Mogą być z tym pewne problemy. Po pierwsze szukam problemu decyzyjnego. Po drugie, w modelu Turinga zwracaniem losowego elementu jest

Ω (n)

$\Omega (n)$ , ponieważ nie ma losowego dostępu. Może maszyna zawsze wysyła pierwszy element? Pierwszy problem jest jednak większy.

— aelguindy

Ostatni akapit nie ma sensu, ponieważ każdy algorytm Las Vegas można przekonwertować na algorytm Monte Carlo.

— Tsuyoshi Ito

Odpowiedzi:

Testowanie tożsamości wielomianowej dopuszcza algorytm losowego wielomianu czasowego (patrz lemat Schwartza-Zippela ), a obecnie nie mamy dla niego deterministycznego algorytmu czasu wielomianowego ani nawet sub wykładniczego algorytmu czasu.

Ocena drzewa gry Rozważ pełne drzewo binarne zwęzłami liści, z których każdy przechowuje wartość 0/1. Węzły wewnętrzne zawierają bramki OR / AND w naprzemiennych poziomach. Można udowodnić za pomocą argumentu przeciwnika, że każdy algorytm deterministyczny musiałby zbadaćwęzły liściw najgorszym przypadku. Istnieje jednak prosty algorytm randomizowany, który wymaga spodziewanego czasu działania Spójrz na slajdy 14–27 wykładu. $n$ $\Omega{(n)}$ $O(n^{0.793})$

Nieświadomy routing w hipersześcianie Rozważ sześcian wwymiarach zawierający wierzchołków. Każdy wierzchołek ma pakiet danych i miejsce docelowe, do którego chce ostatecznie dostarczyć pakiet. Miejsce docelowe wszystkich pakietów jest różne. Nawet w tym przypadku udowodniono, że każda deterministyczna strategia routingu wymagakroków. Istnieje jednak prosta strategia losowa, która z dużym prawdopodobieństwem zakończy się w oczekiwanych krokach. $n$ $N=2^n$ $\Omega{\big(\sqrt{\frac{N}{n}}\big)}$ $O(n)$

Zauważ, że w algorytmach losowych oczekiwany koszt z dużym prawdopodobieństwem (jak np. ) jest odpowiednikiem najgorszego przypadku w praktyce. $E(F(n))$ $Pr[F(n) > 10 \cdot E(F(n))] < \frac{1}{n^2}$

— rizwanhudda
źródło

Ponadto należy wziąć pod uwagę testy do matryc , i jeśli jest . Obecnie nie znamy algorytmu , znamy losowy algorytm . Chodzi o to, czy istnieją problemy, dla których możemy udowodnić, że algorytmy losowe są lepsze?

A

$A$

B

$B$

C

$C$

A B = C

$A B = C$

o (2^{2.3})

$o(2^{2.3})$

O (n^{2})

$O(n^2)$

— aelguindy,

@aelguindy Rozumiem twój punkt widzenia. Jednak w przypadku PIT najbardziej znanym algorytmem deterministycznym jest wykładniczy. I derandomizacja PIT jest ważnym otwartym problemem w teoretycznym CS.

— rizwanhudda

Dodałem ocenę drzewa gry i routing hipersześcianu do postu, dla których randomizowane algorytmy są znacznie lepsze niż determinacyjne odpowiedniki.

— rizwanhudda

OK, jeśli chodzi o ocenę drzewa gry, jeśli dobrze rozumiem, działa w oczekiwanym , prawda? Mam na myśli przypadki, w których będzie działać w . Czy tak jest również w przypadku trzeciego przykładu? Nie pozwalam na lepszy oczekiwany czas, szukam lepszej złożoności w najgorszym przypadku, dozwolonego błędu w danych wyjściowych.

O (n^{0.793})

$O(n^{0.793})$

Ω (n)

$\Omega(n)$

— aelguindy

Więc nie są lepsze w najgorszym przypadku. Chociaż doceniam przykłady, obawiam się, że nie jest to dokładnie to, czego szukam. Przykłady były jednak bardzo pouczające!

— aelguindy

Badanie najgorszego przypadku nie ma znaczenia dla algorytmów losowych. Środowisko wykonawcze w najgorszym przypadku często będzie nieskończone, ale nie będzie w stanie przewyższyć algorytmów deterministycznych w tej metodzie.

Rozważmy dowolny randomizowane algorytm . Uzyskaj deterministyczny algorytm , ustalając losową taśmę dla na . Następnie dla wszystkich . $A$ $B$ $A$ $0^\infty$ $T_B(n) \leq T_A(n)$ $n$

— Raphael
źródło

Istnieje wiele problemów, w których wiemy o wydajnym algorytmie losowym i nie znamy żadnego deterministycznego algorytmu, który możemy udowodnić, że jest skuteczny. Może to jednak odzwierciedlać niedociągnięcia w naszej zdolności do udowodnienia złożoności, a nie jakiejkolwiek zasadniczej różnicy.

Na podstawie Twojego komentarza wydaje się, że chciałeś zapytać, czy istnieje problem z wydajnym algorytmem randomizowanym i możemy udowodnić, że nie ma algorytmu deterministycznego o porównywalnej wydajności. Nie znam żadnego takiego problemu.

Rzeczywiście istnieją uzasadnione podstawy, aby podejrzewać, że takie problemy prawdopodobnie nie wystąpią. Heurystycznie istnienie takiego problemu prawdopodobnie oznaczałoby, że bezpieczna kryptografia jest niemożliwa. To wydaje się raczej nieprawdopodobne.

Jaki jest związek, pytasz? Rozważmy dowolny randomizowany algorytm który skutecznie rozwiązuje jakiś problem. Opiera się na losowych monetach: losowych bitach uzyskanych ze źródła prawdziwie losowego. Załóżmy teraz, że bierzemy generator pseudolosowy o jakości kryptograficznej i zastępujemy źródło prawdziwie losowe wyjściem generatora pseudolosowego. Wywołaj wynikowy algorytm . Należy zauważyć, że jest algorytm deterministyczny, a jego czas pracy jest w przybliżeniu taka sama jak . $A$ $A'$ $A'$ $A$

Ponadto, jeśli kryptograficzny PRNG jest bezpieczny, heurystycznie powinniśmy oczekiwać, że będzie dobrym algorytmem, jeśli jest: $A'$ $A$

Na przykład, jeśli jest algorytmem Las Vegas (zawsze wysyła poprawną odpowiedź i kończy się szybko z dużym prawdopodobieństwem), to będzie całkiem dobrym algorytmem deterministycznym (zawsze wysyła poprawną odpowiedź i kończy się szybko dla większości danych wejściowych) . $A$ $A'$
Jako kolejny przykład, jeśli jest algorytmem Monte Carlo (deterministyczny czas działania i daje prawidłową odpowiedź z prawdopodobieństwem co najmniej ), to będzie całkiem dobrym algorytmem deterministycznym (deterministyczny czas działania i wyświetla prawidłowy wynik odpowiedz na ułamek wszystkich danych wejściowych). $A'$ $1-\varepsilon$ $A$ $1-\varepsilon$

Dlatego jeśli kryptograficzny PRNG jest bezpieczny i istnieje skuteczny algorytm losowy, otrzymasz algorytm deterministyczny, który jest całkiem dobry. Obecnie istnieje wiele konstrukcji kryptograficznych programów PRNG, które mają zagwarantowane bezpieczeństwo, jeśli zostaną spełnione pewne założenia kryptograficzne. W praktyce powszechnie uznaje się te założenia kryptograficzne: przynajmniej bezpieczny handel i transakcje polegają na tym, że są prawdziwe, więc najwyraźniej jesteśmy skłonni obstawiać duże sumy pieniędzy, że istnieje bezpieczna kryptografia. Jedynym sposobem, w jaki ta transformacja może się nie powieść, jest brak kryptograficznego PRNG, co z kolei oznacza, że bezpieczna kryptografia jest niemożliwa. Chociaż nie mamy żadnego dowodu, że tak nie jest, wydaje się to mało prawdopodobnym rezultatem.

Szczegóły konstrukcji: oto jak działa . Na wejściowych , wyprowadza się materiał siewny na PRNG kryptograficznego w funkcji (na przykład, przez mieszający ), a następnie symuluje , do wyjścia z PRNG kryptograficznego jako monet dla . Na przykład określoną instancją byłoby ustawienie , a następnie użycie jako zarodka dla AES256 w trybie licznika lub innego kryptograficznego PRNG. Możemy udowodnić powyższe stwierdzenia w modelu losowej wyroczni. $A'$ $x$ $x$ $x$ $A(x)$ $A$ $k=\text{SHA256}(x)$ $k$

Jeśli nie jesteś zadowolony z pomysłu, że może generować nieprawidłowe wyniki na niewielkiej części danych wejściowych, można to rozwiązać. Jeśli powtórzysz wiele razy i uzyskasz większość głosów, prawdopodobieństwo błędu gwałtownie spada w liczbie iteracji. Tak więc, iterując stałą liczbę razy, możesz uzyskać prawdopodobieństwo błędu poniżej , co oznacza, że szanse, że natkniesz się na dane wejściowe gdy algorytm generuje błędną odpowiedź, są znikomo małe (mniej niż szanse na trafienie pioruna wiele razy z rzędu). Co więcej, przy konstrukcji, którą podałem powyżej, szanse, że przeciwnik może nawet znaleźć wkład $A'$ $A'$ $\varepsilon$ $1/2^{256}$ $x$ $x$ gdzie daje złą odpowiedź, można uczynić bardzo małym, ponieważ wymagałoby to złamania bezpieczeństwa skrótu SHA256. (Technicznie wymaga to modelu losowej wyroczni, aby to uzasadnić, więc oznacza to, że musi być wybrany jako „niezależny” od SHA256, a nie w twardym kodzie obliczeń związanych z SHA256, ale prawie wszystkie rzeczywiste algorytmy spełniają ten wymóg .) $A'$ $A$

Jeśli chcesz mocniejszej podstawy teoretycznej, możesz iterować razy i uzyskać prawdopodobieństwo błędu poniżej , gdzie jest długością wejścia . Teraz ułamek bitowych danych wejściowych, na których daje niepoprawną odpowiedź, jest ściśle mniejszy niż . Ale są tylko możliwych wejść bitowych, a na każdym z nich jest poprawne lub niepoprawne, więc wynika z tego, że nie ma danych wejściowych, w których jest niepoprawne: jest poprawne na wszystkich wejściach, i to bezwarunkowo . Jeśli $A$ $\Theta(n)$ $1/2^n$ $n$ $x$ $n$ $A'$ $1/2^n$ $2^n$ $n$ $A$ $A'$ $A'$ $A$ biegnie w czasie , następnie biegnie w czasie , więc jest nieco wolniejsze niż ale nie za dużo wolniejsze. Jest to treść dowodu Adlemana, że BPP jest zawarty w P / poly. Dla celów praktycznych jest to prawdopodobnie przesada, ale jeśli lubisz czyste dowody, które unikają założeń kryptograficznych lub jeśli podchodzisz do tego z perspektywy teoretyka, możesz polubić tę wersję bardziej. $t(n)$ $A'$ $\Theta(n \cdot t(n))$ $A'$ $A$

Aby uzyskać więcej informacji na temat ostatnich rozważań teoretycznych i dodatkowych problemów, w przypadku których znamy skuteczny algorytm randomizowany, ale nie znamy żadnego deterministycznego algorytmu, który możemy udowodnić, że jest skuteczny, zobacz /cstheory//q/31195 / 5038

Podsumowując: W przypadku każdego problemu, w którym znamy skuteczny algorytm randomizowany, znamy również algorytm deterministyczny, który wydaje się być skuteczny w praktyce - ale obecnie nie wiemy, jak udowodnić , że jest skuteczny. Jedną z możliwych interpretacji jest to, że nie jesteśmy zbyt dobrzy w dowodzeniu rzeczy na temat algorytmów.

— DW
źródło