Existenz eines Pseudozufallsgenerators

Question

Wie man das zeigt für $\epsilon>0$gibt es eine Funktion $G:\{0,1\}^n->\{0,1\}^{2^{\epsilon n}}$ das ist ein $2^{\epsilon n}$-prg, ohne die Bedingung, die in berechenbar ist $2^{O(n)}$Zeit. Was ich zu zeigen versuche, ist mit hoher Wahrscheinlichkeit, wenn wir nehmen$\epsilon=1/10$, eine zufällige $G$erfüllt diese Bedingung. Aber um das zu zeigen, müssen wir keine Schaltkreise von Größe zeigen$<2^{3/10n}$ sind in der Lage, zwischen gleichmäßiger Längenverteilung zu unterscheiden $2^{n/10}$ und Ausgabe von $G$. Das kann ich nicht bekommen. Kann mir jemand einen Ansatz geben?

Answer 1

Wenn du wählst $G$ ab der gleichmäßigen Zufallsverteilung $\{0, 1\}^n \to \{0, 1\}^{2^{\epsilon n}}$ ohne Einschränkungen kann dann nichts (richtig) zwischen der gleichmäßigen Verteilung und der Ausgabe von unterscheiden $G$, weil du es per Definition einheitlich zufällig gemacht hast. Zu diesem Zeitpunkt ist die Ausgabe von$G$ist nicht mehr pseudozufällig, es ist zufällig.