Sự tồn tại của Pseudorandom Generator

Question

Làm thế nào để hiển thị điều đó cho $\epsilon>0$, tồn tại một chức năng $G:\{0,1\}^n->\{0,1\}^{2^{\epsilon n}}$ đó là một $2^{\epsilon n}$-prg, không có điều kiện có thể tính toán được trong $2^{O(n)}$thời gian. Những gì tôi đang cố gắng thể hiện là với xác suất cao, nếu chúng tôi$\epsilon=1/10$, một ngẫu nhiên $G$thỏa mãn điều kiện này. Nhưng để cho thấy điều đó, chúng ta cần chỉ ra rằng, không có mạch nào có kích thước$<2^{3/10n}$ có thể phân biệt giữa sự phân bố đồng đều về chiều dài $2^{n/10}$ và đầu ra của $G$. Điều này tôi không thể có được. Bất cứ ai có thể cho tôi một cách tiếp cận?

Answer 1

Nếu bạn chọn $G$ từ phân phối ngẫu nhiên đồng nhất trên $\{0, 1\}^n \to \{0, 1\}^{2^{\epsilon n}}$ không có hạn chế, thì không gì có thể (một cách chính xác) phân biệt giữa phân phối đồng đều và đầu ra của $G$, bởi vì bạn đã làm cho nó ngẫu nhiên đồng nhất theo định nghĩa. Tại thời điểm này, đầu ra của$G$không còn là giả ngẫu nhiên nữa, nó là ngẫu nhiên.