Losowa samoredukowalność

Losowa samoredukowalność (RSR) to zasada, zgodnie z którą dobry algorytm dla średniego przypadku implikuje dobry algorytm dla najgorszego przypadku. RSR to zdolność do rozwiązania wszystkich przypadków problemu poprzez rozwiązanie dużej części przypadków.

Definicja

Jeśli dla funkcji f oceniającej dowolną instancję x można zredukować w czasie wielomianowym do oceny f w jednym lub większej liczbie losowych instancji y i , to jest ona samoredukowalna (jest to również znane jako nieadaptacyjna jednolita samoredukcja ) . W losowej autoredukcji dowolny najgorszy przypadek x w domenie f jest odwzorowywany na losowy zbiór przypadków y 1 , ..., y k . Robi się to tak, że f ( x ) można obliczyć w czasie wielomianowym, biorąc pod uwagę sekwencję rzutów monetą z odwzorowania, x i f ( y 1 ), ..., f ( y k ). Dlatego biorąc średnią w odniesieniu do indukowanego rozkładu na y i , średnia złożoność przypadku f jest taka sama (w ramach czynników wielomianowych) jak złożoność losowa f w najgorszym przypadku .

Szczególnym przypadkiem wartym odnotowania jest przypadek, gdy każda przypadkowa instancja y i jest równomiernie rozłożona w całym zbiorze elementów w dziedzinie f , które mają długość | x |. W tym przypadku f jest średnio tak trudne, jak w najgorszym przypadku. Podejście to zawiera dwa kluczowe ograniczenia. Najpierw generowanie y 1 , ..., y k odbywa się nieadaptacyjnie. Oznacza to, że y 2 jest wybierane przed f ( y 1 ) jest znana. Po drugie, nie jest konieczne, aby punkty y 1 , ..., y k były rozmieszczone równomiernie.

Zastosowanie w protokołach kryptograficznych

Problemy, które wymagają pewnej prywatności w danych (zwykle problemy kryptograficzne ) mogą wykorzystywać randomizację, aby zapewnić tę prywatność. W rzeczywistości jedyny możliwy do udowodnienia bezpieczny system kryptograficzny ( jednorazowa podkładka ) ma swoje bezpieczeństwo całkowicie oparte na losowości kluczowych danych dostarczanych do systemu.

Dziedzina kryptografii wykorzystuje fakt, że pewne funkcje teorii liczb są losowo samoredukowalne. Obejmuje to szyfrowanie probabilistyczne i silne kryptograficznie generowanie liczb pseudolosowych . Również schematy ukrywania instancji (gdzie słabe urządzenie prywatne używa silnego urządzenia publicznego bez ujawniania jego danych) można łatwo zilustrować losowymi samoredukcjami.

Przykłady

Problem logarytmu dyskretnego , problem resztek kwadratowych , problem inwersji RSA i problem obliczania stałej macierzy to losowe problemy samoredukowalne.

Dyskretny logarytm

Twierdzenie : Dana grupa cykliczna G o rozmiarze | G |. Jeśli deterministyczny algorytm czasu wielomianowego A oblicza logarytm dyskretny dla ułamka 1/poli( n ) wszystkich danych wejściowych (gdzie n = log | G | jest wielkością wejściową), to istnieje algorytm losowego czasu wielomianowego dla logarytmu dyskretnego dla wszystkich wejścia.

Biorąc pod uwagę generator g grupy cyklicznej G = { g i | 0 ≤ ja < | G | } i an x ​​∈ G , dyskretny logarytm x do podstawy g jest liczbą całkowitą k (0 ≤ k < | G |) gdzie x = g k . Przyjmijmy, że B ma rozkład równomierny na {0,...,| G | − 1}, wtedy xg B = g k + B jest również równomiernie rozłożone na G . Zatem xg B jest niezależne od x , a jego logarytm można obliczyć z prawdopodobieństwem 1/poli( n ) w czasie wielomianowym. Wtedy log g x ≡ log g xg B - B (mod | G |) i logarytm dyskretny jest samoredukowalny.

Stała matrycy

Biorąc pod uwagę definicję permanentu macierzy , jasne jest, że PERM ( M ) dla dowolnej n -na- n macierzy M jest wielomianem wielowymiarowym stopnia n nad wpisami w M . Obliczenie stałej macierzy jest trudnym zadaniem obliczeniowym — PERM jest #P-zupełny ( dowód ). Ponadto umiejętność obliczania PERM ( M ) dla większości macierzy implikuje istnienie losowego programu, który oblicza PERM ( M ) dla wszystkich macierzy. To pokazuje, że PERM jest losowo samoredukowalny. Poniższe omówienie dotyczy przypadku, w którym wpisy macierzy są rysowane ze skończonego ciała F p dla pewnej liczby pierwszej p i gdzie cała arytmetyka jest wykonywana w tym ciele.

Niech X będzie losową macierzą n -na- n z wpisami z F p . Ponieważ wszystkie elementy dowolnej macierzy M + kX są funkcjami liniowymi k , łącząc te funkcje liniowe z wielomianem wielowymiarowym stopnia n , który oblicza PERM ( M ) , otrzymujemy kolejny wielomian stopnia n na k , który będziemy nazywać p ( k ) . Jasne, str (0) jest równe permanentowi M .

Załóżmy, że znamy program, który oblicza poprawną wartość PERM ( A ) dla większości n -na- n macierzy z wpisami z F p ---konkretnie, 1 − 1/(3 n ) z nich. Następnie z prawdopodobieństwem około dwóch trzecich możemy obliczyć PERM ( M + kX ) dla k = 1,2,..., n + 1. Kiedy już mamy te wartości n + 1, możemy rozwiązać współczynniki p ( k ) za pomocą interpolacja (pamiętaj, że p ( k ) ma stopień n ). Kiedy dokładnie znamy p ( k ), oceniamy p (0), które jest równe PERM ( M ).

Jeśli to zrobimy, ryzykujemy, że popełnimy błąd w 1/3 przypadków, ale wybierając wiele losowych X i powtarzając powyższą procedurę wiele razy i podając tylko zwycięzcę większości jako odpowiedź, możemy zwiększyć poziom błędu w dół bardzo nisko.

Konsekwencje

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Random_self-reducibility&oldid=859390116 ”