Esistenza di Pseudorandom Generator

Question

Come dimostrarlo per $\epsilon>0$, esiste una funzione $G:\{0,1\}^n->\{0,1\}^{2^{\epsilon n}}$ cioè un $2^{\epsilon n}$-prg, senza la condizione che è calcolabile in $2^{O(n)}$tempo. Quello che sto cercando di mostrare è con alta probabilità, se lo prendiamo$\epsilon=1/10$, un casuale $G$soddisfa questa condizione. Ma per dimostrarlo, dobbiamo mostrare, nessun circuito di dimensioni$<2^{3/10n}$ sono in grado di distinguere tra distribuzione uniforme della lunghezza $2^{n/10}$ e l'output di $G$. Questo non sono in grado di ottenerlo. Qualcuno può darmi un approccio?

Answer 1

Se scegli $G$ dalla distribuzione casuale uniforme in poi $\{0, 1\}^n \to \{0, 1\}^{2^{\epsilon n}}$ senza restrizioni, allora niente può (correttamente) distinguere tra la distribuzione uniforme e l'output di $G$, perché lo hai reso uniformemente casuale per definizione. A questo punto l'uscita di$G$non è più pseudo-casuale, è casuale.