# What is the largest "allowed" seed for a PRNG to not give any extra power to a deterministic machine?

Suppose a polynomial time machine that has an access to a polynomially long string of bits independent on the input. On average, it's impossible to compress this string to a subpolynomially long string using a deterministic polynomial time compression algorithm.

As far as I understand, such a machine would be a $$BPP$$ machine, even though the source of bits is not necessarily a random number generator.

In this case the amount of independent bits is polynomial. I suppose, if we allow only a constant amount of independent bits (e.g. how it happens with most existing PRNGs using system time - a fixed length independent string - for a seed) then the PRNG gives no extra computation power. However, can it be above constant and still keep the machine equal to a polynomial time deterministic machine?

I think there must be some confusion in the problem setting. Given an input of $$n$$ bits chosen uniformly at random, there is no algorithm to compress it to something whose length is on average shorter than $$n$$ bits. This is a pure information theoretic fact, that holds regardless of how much computation power you throw at the problem. So I think your formulation in terms of compression is not accurately capturing what you actually care about.
Any program that uses only a random seed of length $$O(\log n)$$ can be derandomized, by trying all $$2^{O(\log n)}=O(\text{poly}(n))$$ possibilities for the seed. So a seed length of up to $$O(\log n)$$ bits does not add extra power.
• "there is no algorithm to compress it to something whose length is on average shorter than $n$ bits" - yes, of course, I just don't know if uniform randomness is even required. In that sense incompressibility is probably a weaker requirement, or maybe equivalent. Commented Nov 28, 2023 at 8:05