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?


1 Answer 1


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.

It is an open question to what extent derandomization is possible. There is work relating derandomization and the existence of pseudorandom generators, which might be of interest to you.

  • $\begingroup$ "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. $\endgroup$
    – rus9384
    Commented Nov 28, 2023 at 8:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.