What is and amplification factor in pseudo-random generators?

Question

I can't seem to find an answer to this. For instance, I have this question:

Show that, if $P=NP$, there aren't any pseudo-random generators (even with amplification factor $n+1$).

My gut tells me this is because, in a world where $P=NP$, pretty much any process can be efficiently inverted so there aren't one-way functions (which pseudo-random generators rely on).

Answer 1

Amplification is equivalent to "stretch", the number of (seemingly) random bits that your algorithm generates given the truly random seed.

Let $G:\{0,1\}^*\rightarrow\{0,1\}^*$ be a PRG that maps strings of length $n$ to strings of length $l(n)$, then $l(n)$ is said to be the stretch function of $G$. If $l(n)>n$ and $l$ is injective, then you have $\forall n :|Im(G)\cap\{0,1\}^n|\le 2^{n-1}$. You can use this to construct a language $L\in NP$, such that $L\in P$ allows you to break $G$ (construct a distinguisher with success probability $\ge\frac{1}{2})$. Note that you can relax the injectivity requirement by ignoring some of the output (i.e. given a PRG with stretch $l(n)>n$, you can construct a PRG with stretch $l'(n)=n+1$).