Keberadaan Generator Pseudorandom

Question

Bagaimana menunjukkan itu untuk $\epsilon>0$, ada fungsi $G:\{0,1\}^n->\{0,1\}^{2^{\epsilon n}}$ itu adalah $2^{\epsilon n}$-prg, tanpa kondisi yang dapat dihitung dalam $2^{O(n)}$waktu. Apa yang saya coba tunjukkan adalah dengan probabilitas tinggi, jika kita ambil$\epsilon=1/10$, secara acak $G$memenuhi kondisi ini. Tetapi untuk menunjukkan itu, kita perlu menunjukkan, tidak ada sirkuit ukuran$<2^{3/10n}$ mampu membedakan antara distribusi panjang yang seragam $2^{n/10}$ dan keluaran $G$. Ini saya tidak bisa mendapatkan. Adakah yang bisa memberi saya pendekatan?

Answer 1

Jika Anda memilih $G$ dari distribusi acak seragam pada $\{0, 1\}^n \to \{0, 1\}^{2^{\epsilon n}}$ tanpa batasan, maka tidak ada yang dapat (dengan benar) membedakan antara distribusi seragam dan keluaran $G$, karena Anda membuatnya acak secara seragam menurut definisi. Pada titik ini, keluaran$G$tidak lagi pseudo-acak, itu adalah acak.