1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Emil Jeřábek Mar 27 at 8:18
  • $\begingroup$ 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 $\endgroup$ – domotorp Mar 27 at 8:22
  • $\begingroup$ @domotorp make this into an answer? Possibly add people.seas.harvard.edu/~salil/pseudorandomness $\endgroup$ – usul Mar 27 at 14:17
  • $\begingroup$ by the way, Shannon entropy doesn't seem to be the right notion for randomness used by BPP algorithms., e.g. X=00...0 with very high probability and uniform otherwise has very high Shannon entropy, not useful. So if we have non-uniform bits, they're often measured with min-entropy. en.wikipedia.org/wiki/Min-entropy $\endgroup$ – usul Mar 27 at 15:09
  • $\begingroup$ Emil: Uniforms strings of bits would just mean that entropy would coinside with bit length. The number of random bits needed to solve the problem is a consumed resource. If you think about algorithms that solve BPP problems you can write them with a "get_random_bit" function that returns the next bit in the string. usul: Good catch on the bit strings being non-uniform. I was thinking about each bit being IID but other sources of randomness certainly exist. Certainly min-entropy would solve that issue and is identical for the uniform case. $\endgroup$ – Jake Mar 27 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.