# Why can't we just compose PRGs to get better PRGs?

I'm learning about (complexity-theoretic) pseudorandom number generators, and I have a pretty basic question about them that I couldn't find an answer to.

Let's say we have a PRG for $$P$$ that can fool any algorithm running over $$n$$ bits in time $$poly(n)$$ with seed length $$O(\log^{10}(n))$$. This would already be a breakthrough, as it would imply $$BPP$$ can be decided in deterministic polylog time. But why stop there? Now, every algorithm in $$BPP$$ only needs $$O(\log^{10}(n))$$ truly random bits -- why not just use our existing PRG again, so that we only need $$O(\log^{10}(O(\log^{10}(n)))) = O(\log\log(n)^{10}) \subset o(\log(n))$$ bits, and then $$P = BPP$$? (I'm not seriously suggesting this is possible; I'm trying to understand the flaw in the reasoning.)

One immediate concern is that if we use $$o(\log(n))$$ random bits at the end, the distinguisher could just memorize the correct words. But is that the only obstacle? Does that mean if we had a PRG with a "half-logarithmic" seed length, we could do the above strategy?

In general, why can't we just compose PRGs to get arbitrarily better PRGs?

• What is $n$? Please define all notation.
– D.W.
Commented Jan 19, 2023 at 19:57
• @D.W. I have updated the question to define $n$.
– Jake
Commented Jan 19, 2023 at 21:04

Short answer: you can enumerate all possible seeds of length $$O(\log^{10}(\log^{10}(n)))$$ in $$\text{poly}(\log n)$$ time, so such a PRG cannot possible be secure against algorithms whose running time is polynomial in $$\log n$$, so such a PRG tells us nothing about BPP.
Longer answer: a PRG is a family of functions that are associated with three quantities, the input length, the output length, and an upper bound on the adversary's running time. Typically, each of these may be a function of $$n$$. The guarantee is that the PRG will be secure against all adversaries whose running time is upper-bounded by the corresponding value. So, to make your argument more concrete, work out what are those values (especially, check out how the security level -- the upper bound on adversary running time -- of the composition of two PRGs depends on the security level of the underlying PRGs), and work out what they need to be for your claim about implications for BPP to hold, and you'll probably spot the issue.