Randomizowany algorytm, który „wygląda” deterministycznie?

Czy istnieje interesujący przykład losowego algorytmu dla problemu wyszukiwania, który zawsze generuje tę samą (poprawną) odpowiedź, niezależnie od wewnętrznej losowości, ale który wykorzystuje losowość, dzięki czemu jej oczekiwany czas działania jest lepszy niż czas działania najszybszego znanego algorytm deterministyczny dla problemu?

W szczególności zastanawiałem się, czy istnieje taki algorytm do znajdowania liczby pierwszej między n a 2n. Nie jest znany algorytm deterministyczny wielomianu czasu. Istnieje trywialny algorytm losowy, który działa po prostu próbkując losowe liczby całkowite w przedziale, który działa dzięki twierdzeniu o liczbie pierwszej . Ale czy istnieje algorytm powyższego rodzaju, którego oczekiwany czas działania jest pośredni między nimi?

EDYCJA: Aby nieco zawęzić moje pytanie, chciałem takiego algorytmu dla problemu, w którym istnieje wiele możliwych poprawnych wyników, a jednak algorytm losowy ustawia się na jednym niezależnie od jego losowości. Zdaję sobie sprawę, że pytanie prawdopodobnie nie jest w pełni określone ...

Shafi Goldwasser poinformowała mnie, że ona i współautorzy badali dokładnie takie algorytmy w przypadku problemów teoretycznych! Znane są następujące:

1. Lenstra wykazał, że istnieje taki algorytm do znajdowania kwadratycznego modu nieresztkowego w danej liczbie pierwszej.

2. Gat i Goldwasser pokazali, że istnieje taki algorytm znajdowania generatora , gdzie jest daną liczbą pierwszą postaci dla liczby pierwszej .$\mathbb{Z}_p^*$$p$$2q + 1$$q$

(Nie znam cytowanych odniesień.) Trwają również badania nad pytaniem, które zadałem o znalezienie liczby pierwszej między a .$n$$2n$

EDYCJA: Artykuł Gat i Goldwassera został teraz opublikowany: http://eccc.hpi-web.de/report/2011/136/ . Ten artykuł nie rozwiązuje jednak problemu znalezienia liczby pierwszej między a .$n$$2n$

Czy liczą się losowe struktury danych?

Istnieje lista pominięć, która jest posortowaną strukturą danych mapy asocjacyjnej.

Jego czas wykonywania typowych operacji, takich jak wstawianie, pobieranie i usuwanie, jest (w oczekiwanym przypadku) na równi z tymi w zrównoważonych drzewach wyszukiwania - tj. . Jednak czasami twierdzi się, że struktura danych ma o wiele lepszy stały współczynnik niż implementacje drzewa wyszukiwania, jeśli jest wykonana właściwie (zależy to krytycznie od dobrego i wydajnego źródła losowości). Lepszy stały współczynnik prawdopodobnie wynika z faktu, że nie trzeba przeprowadzać ponownego równoważenia (ani żadnej podobnej operacji).$O(\log n)$

A co z losowym algorytmem simpleksów wielomianowych Kelnera i Spielmana? Znajduje optymalny wierzchołek programu liniowego. Nie jest znany żaden deterministyczny algorytm simpleksowy, który działałby w czasie wielomianowym, a dla wielu z nich można skonstruować instancje patologiczne, które powodują, że algorytm zajmuje czas wykładniczy.

Oczywiście istnieją algorytmy punktu wewnętrznego w czasie wielomianowym, więc nie jest to dokładnie to, czego szukasz.

Rozważ kompletne drzewo binarne ze wszystkimi liśćmi zawierającymi 0, z wyjątkiem jednego liścia zawierającego 1. Zadaniem jest znalezienie liścia zawierającego 1. Przeciwko dowolnemu deterministycznemu algorytmowi wyszukiwania można zbudować nieskończoną rodzinę drzew (po jednym dla każdego n ) dla których algorytm musi sprawdzać każdy liść. Tak więc dla tej najgorszej rodziny algorytm deterministyczny oczekiwał czasu działania 2 n .$2^n$$n$$2^n$

Rozważmy teraz algorytm, który losowo wybiera pierwszy liść losowo równomiernie, a następnie deterministycznie sprawdza wszystkie kolejne liście (zawijając do początku). Znajdzie to 1 po zbadaniu średnio połowy wszystkich liści. Zatem zrandomizowany algorytm oczekiwał czasu działania .$2^{n-1}$

Czy to się kwalifikuje?

Algorytmy faktoryzacji wielomianowej mogą być przykładem, którego szukasz. W Cantora Zassenhaus algorytm zastosowania przypadkowości w celu obliczenia (unikalny zapisu do skalowania) nieredukowalnych współczynników wielomianowych danego jednoczynnikowej wielomian przez skończonego w czasie wielomianem względem wielkości sygnału wejściowego i log P . Jeśli naprawdę chcesz, aby problem miał unikalną odpowiedź, możesz poprosić o moniczne nieredukowalne czynniki pierwsze wielomianu monicznego. O ile mi wiadomo, nie wiadomo, jak uwzględniać deterministyczny czas wielomianowy, chyba że p jest gwarantowane, że jest małe.$\mathbb{F}_p$$\log p$$p$

$\log p$

Był projekt polimath dotyczący podobnego pytania: http://michaelnielsen.org/polymath1/index.php?title=Finding_primes

Jeśli chodzi o twoje pierwsze pytanie, najpierw pomyślałem o Quicksort, ale to powinno być oczywiste.

Istnieje algorytm dopasowywania ciągów ( Nebel, 2006 ), który wykorzystuje idee probabilistyczne. Wiem jednak, że jest to najszybsze dostępne podejście i najwyraźniej potrzebujesz próbek do treningu.

Poniższy artykuł STACS '97 może być interesujący w twoim przypadku: Złożoność generowania instancji testowych .

Streszczenie: Ostatnio Watanabe zaproponował nową platformę do testowania poprawności i średniego zachowania przypadków w algorytmach, które mają na celu średnio efektywne rozwiązanie danego problemu wyszukiwania NP. Chodzi o to, aby losowo generować certyfikowane instancje w sposób podobny do podstawowej dystrybucji. Omawiamy to podejście i pokazujemy, że instancje testowe mogą być generowane dla każdego problemu wyszukiwania NP z nieadaptacyjnymi zapytaniami do wyroczni NP. Ponadto, przedstawiamy generatory instancji testowych Las Vegas oraz Monte Carlo i pokazujemy, że można ich użyć, aby dowiedzieć się, czy algorytm jest poprawny i wydajny średnio. W rzeczywistości nie jest trudno zbudować generatory Monte Carlo dla wszystkich problemów związanych z wyszukiwaniem RP, a także generatory Las Vegas dla wszystkich problemów związanych z wyszukiwaniem ZPP. Z drugiej strony,

W szczególności spójrz na stronę 384, w następstwie 12:

$\rm{ZPP}$$\rm{RP}$$\rm{ZPP}$$\rm{NP}$$\rm{NP} \cap \rm{coNP}$

$\frac{1}{n^c}$$\text{polylog}(n)$