Existência de gerador pseudo-aleatório

Question

Como mostrar isso para $\epsilon>0$, existe uma função $G:\{0,1\}^n->\{0,1\}^{2^{\epsilon n}}$ Aquilo é um $2^{\epsilon n}$-prg, sem a condição que é computável em $2^{O(n)}$Tempo. O que estou tentando mostrar é com alta probabilidade, se tomarmos$\epsilon=1/10$, aleatório $G$satisfaz esta condição. Mas, para mostrar isso, precisamos mostrar, nenhum circuito de tamanho$<2^{3/10n}$ são capazes de distinguir entre distribuição uniforme de comprimento $2^{n/10}$ e saída de $G$. Isso eu não sou capaz de obter. Alguém pode me dar uma abordagem?

Answer 1

Se você escolher $G$ da distribuição aleatória uniforme em $\{0, 1\}^n \to \{0, 1\}^{2^{\epsilon n}}$ sem restrições, então nada pode (corretamente) distinguir entre a distribuição uniforme e a saída de $G$, porque você o tornou uniformemente aleatório por definição. Neste ponto, a saída de$G$não é mais pseudo-aleatório, é aleatório.