Jaka jest motywacja definicji pseudolosu w Nisan / Wigderson?

Czytam klasyczny utwór „Twardość kontra losowość” Nisana i Wigdersona. Niech $B=\{0,1\}$ , a ustalenie funkcją $l\colon \mathbb{N} \to \mathbb{N}$ . Określają one rodzinę funkcji $G = \{G_n : B^{l(n)} \to B^n\}$ być pseudolosowe w przypadku każdego obwodu wielkości $n$ mamy

$(*) \ \ | P(C(x) = 1) - P(C(G(y))=1) | < 1/n$

(gdzie $x \in B^{n},y \in B^{l(n)}$ to jednolite zmienne losowe).

Rozumiem, że jestem myśleć o i Y jako zmiennych losowych, i że chcę, aby porównać odległości między i jako zmienne losowe. Rozumiem intuicję, że obwody są używane jako swego rodzaju „testy”, aby sprawdzić, czy można „rozgryźć”. Naprawdę walczę z tym, dlaczego warunek jest właściwy. Czy ktoś ma jakieś porady, jak myśleć o tej definicji?$x$$y$$x$$G(y)$$G$$(*)$

Należy wspomnieć o dwóch aspektach.

Pierwszym z nich jest ogólna idea zdefiniowania PRG, ponieważ jego moc wyjściowa wygląda inaczej niż jednolita dla małych obwodów . Pomysł ten powraca do Yao i jest naprawdę najsilniejszą możliwą definicją, o którą można poprosić, gdy wyraźnie dąży się do pseudolosowości obserwatorów ograniczonych obliczeniowo .

Drugim aspektem jest wybór parametrów, w których ograniczamy wielkość obwodu do a różnica prawdopodobieństwa akceptacji wynosi 1 / n , gdzie n jest również wielkością wyjściową PRG. Wybór ten jest nieco inny niż zwykły kryptograficznego, której wielkość jest obwód s O l a ( n ) , a różnica prawdopodobieństwo muszą być mniejsze niż P ° l r ( n ) . W naszym przypadku konkretnych parametrów (zamiast s O l r ( n $n$$1/n$$n$$poly(n)$$poly(n)$$poly(n)$) były potrzebne, aby uzyskać najostrzejsze wyniki, w tym w szczególności symulacje wielomianowe. Chociaż w zasadzie można mieć 3 różne parametry, okazało się, że nasze wyniki działały zasadniczo w ten sam sposób, więc złożyliśmy je do jednego (oprócz wielkości wejściowej która była postrzegana jako funkcja n ).$l(n)$$n$

W żadnym wypadku nie jestem ekspertem w tej dziedzinie, ale kluczowym elementem definicji pseudolosowości (w przeciwieństwie do prób określenia losowości) jest to, że celem czegoś „pseudolosowego” jest oszukiwanie obwodu. Innymi słowy, motywacją jest pomyślenie, że pseudolosowy ciąg jest dostarczany do obwodu zamiast prawdziwie losowego ciągu.

W tym sensie nie jest tak naprawdę, że próbujesz udawać, że i G ( y ) „wyglądają tak samo”. Chodzi o to, że „wyglądają tak samo” w obwodzie (o koniecznie ograniczonej złożoności).$x$$G(y)$

Rola obwodu jest więc kluczowa, a nie tylko „funkcja testowa”.

Mam nadzieję, że trochę poszerzę odpowiedź Suresha. Po pierwsze, nie sądzę, że surowość nierówności jest potrzebne w swojej , a ja też nie wiem, dlaczego 1 / n jest potrzebna, a nie 1 / 2 n lub coś innego. Jednak praktycznie uważam, że 1 / n wystarczy, aby uzyskać interesujące wyniki teoretyczne.$(*)$$1/n$$1/2n$

Ale wtedy prawie na pewno chcesz stwierdzić, że każdy jest obliczalny w pewnym okresie czasu, powiedzmy wykładniczo. Ponadto myślę, że będziesz musiał potwierdzić, że l ( n ) < n . Możesz myśleć o l ( n ) jako długości nasion. Tak więc G i jest pseudolosowych jeżeli można zwiększyć liczbę bitów w sposób losowy ciągiem o długości L ( n ) nie jest wykrywany przez układ o wielkości mniejszej niż n .$G_i$$l(n) < n$$l(n)$$G_i$$l(n)$$n$