Existence of Pseudorandom Generator How to show that for $\epsilon&gt;0$, there exists a function $G:\{0,1\}^n-&gt;\{0,1\}^{2^{\epsilon n}}$ that is a $2^{\epsilon n}$-prg, without the condition that is is computable in $2^{O(n)}$ time. What I am trying to show is with high probability, if we take $\epsilon=1/10$, a random $G$ satisfies this condition. But in order to show that, we need to show, no circuits of size $&lt;2^{3/10n}$ are able to distinguish between uniform distribution of length $2^{n/10}$ and output of $G$. This I am not able to get. Can anyone give me an approach?
If you choose $G$ from the uniform random distribution on $\{0, 1\}^n \to \{0, 1\}^{2^{\epsilon n}}$ without restrictions, then nothing can (correctly) distinguish between the uniform distribution and the output of $G$, because you made it uniformly random by definition. At this point the output of $G$ is no longer pseudo-random, it is random.