# Entropy bounds on solutions to problems in BPP and other complexity classes based on entropy demands

Has anyone studied the asymptotics of problems in complexity classes like $$BPP$$? The thought came to me that if a problem in $$BPP$$ only requires $$O(log(n))$$ bits of entropy to solve then, intuitively, you should be able to generate every bit string of length $$k*log(n)$$ for some $$k$$ and use those bits to simulate a probabilistic algorithm which solves the problem for each bit string. Then if the algorithm was written correctly the correct result should occur in greater than $$\frac{2}{3}$$ of the cases you ran the input on. It might be the case that every problem in $$BPP$$ can be solved with $$O(log(n))$$ bits of entropy which I think would lead to a proof that $$P = BPP$$. On the same token it seems possible that there might exist an algorithm that requires $$O(n)$$ bits of entropy. This seems like it might provide a reason for the separation between P and BPP which seems unlikely.

This also just in general seems like a resource to think about the asymptotics of that I hadn't thought about before and I'd be generally interested in learning about what has been done in this area. There are some easy things we can conclude from the start like every solution to a problem in $$BPP$$ uses at most $$O(n^c)$$ bits of entropy since you can branch on at most $$O(n^c)$$ bits if your running time is $$O(n^c)$$. As outlined above though I suspect it must be the case that every problem in $$BPP$$ can be solved in $$O(log(n))$$ bits of entropy.

Are any lower bounds on entropy requirements for problems in BPP known? Is there any material on this general area I could read? Is there a known proof that if a probabilistic algorithm requires at most $$O(log(n))$$ bits of entropy then it has a deterministic counterpart that solves the same problem in $$P$$? Is there a proof that if there exists a problem in $$BPP$$ that requires $$O(n)$$ bits then $$P \ne BPP$$ (that would also imply P != NP so obviously something isn't proven there). If not Shannon entropy then perhaps min-entropy?

• I don’t understand what you are trying to do. BPP algorithms do not consume abstract “entropy”, they consume a sequence of independent uniformly random bits. Are you trying to feed a BPP algorithm with a nonuniform source of randomness of some given entropy, or what? Mar 27 '19 at 8:18
• These ideas are not knew and, of course, the problem is still unsolved. Some links: pdfs.semanticscholar.org/02e0/… math.ias.edu/~avi/BOOKS/rand.pdf Mar 27 '19 at 8:22