<p>Has anyone studied the asymptotics of problems in complexity classes like <span class="math-container">$BPP$</span>? The thought came to me that if a problem in <span class="math-container">$BPP$</span> only requires <span class="math-container">$O(log(n))$</span> bits of entropy to solve then, intuitively, you should be able to generate every bit string of length <span class="math-container">$k*log(n)$</span> for some <span class="math-container">$k$</span> 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 <span class="math-container">$\frac{2}{3}$</span> of the cases you ran the input on. It might be the case that every problem in <span class="math-container">$BPP$</span> can be solved with <span class="math-container">$O(log(n))$</span> bits of entropy which I think would lead to a proof that <span class="math-container">$P = BPP$</span>. On the same token it seems possible that there might exist an algorithm that requires <span class="math-container">$O(n)$</span> bits of entropy. This seems like it might provide a reason for the separation between P and BPP which seems unlikely.</p>

<p>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 <span class="math-container">$BPP$</span> uses at most <span class="math-container">$O(n^c)$</span> bits of entropy since you can branch on at most <span class="math-container">$O(n^c)$</span> bits if your running time is <span class="math-container">$O(n^c)$</span>. As outlined above though I suspect it must be the case that every problem in <span class="math-container">$BPP$</span> can be solved in <span class="math-container">$O(log(n))$</span> bits of entropy.</p>

<p>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 <span class="math-container">$O(log(n))$</span> bits of entropy then it has a deterministic counterpart that solves the same problem in <span class="math-container">$P$</span>? Is there a proof that if there exists a problem in <span class="math-container">$BPP$</span> that requires <span class="math-container">$O(n)$</span> bits then <span class="math-container">$P \ne BPP$</span> (that would also imply P != NP so obviously something isn't proven there). If not Shannon entropy then perhaps min-entropy?</p>

CC BY-SA 4.0
2019-03-27T08:18:56.237Z
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?
Emil Jeřábek
CC BY-SA 4.0
2019-03-27T08:22:58.953Z
These ideas are not knew and, of course, the problem is still unsolved. Some links:
https://pdfs.semanticscholar.org/02e0/bb1ff6513c99456ef3943e7a63ddb20afe3e.pdf
http://www.math.ias.edu/~avi/BOOKS/rand.pdf
domotorp
CC BY-SA 4.0
2019-03-27T14:17:51.097Z
@domotorp make this into an answer? Possibly add http://people.seas.harvard.edu/~salil/pseudorandomness/
usul
CC BY-SA 4.0
2019-03-27T15:09:56.400Z
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. https://en.wikipedia.org/wiki/Min-entropy
usul
CC BY-SA 4.0
2019-03-27T21:07:32.283Z
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.
Jake
CC BY-SA 4.0
2019-03-28T08:29:08.390Z
So the answer to my comment is “yes, I’m trying to feed a BPP algorithm with a nonuniform source of randomness”?
Emil Jeřábek
CC BY-SA 4.0
2019-03-28T08:53:11.630Z
Are you aware of the existence of randomness extractors (see e.g. https://cs.haifa.ac.il/~ronen/online_papers/ICALPinvited.pdf)? Basically, a random source with min-entropy $k$ is not much different from a uniform $k$-bit source.
Emil Jeřábek
CC BY-SA 4.0
2019-03-30T05:57:40.703Z
@Emil, the answer is I don't care either way, they're equivalent and you can answer in terms of bit lengths if you'd like.
Jake
<cc.complexity-theory><ds.algorithms><reference-request><lower-bounds><shannon-entropy>
Entropy bounds on solutions to problems in BPP and other complexity classes based on entropy demands
Jake
# Entropy bounds on solutions to problems in BPP and other complexity classes based on entropy demands

(Asked by: username_0 on 2019-03-27)

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?

**Tags:** cc.complexity-theory, ds.algorithms, reference-request, lower-bounds, shannon-entropy
> **Comments:**
> **username_1**: 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?  
> **username_2**: These ideas are not knew and, of course, the problem is still unsolved. Some links: https://pdfs.semanticscholar.org/02e0/bb1ff6513c99456ef3943e7a63ddb20afe3e.pdf http://www.math.ias.edu/~avi/BOOKS/rand.pdf  
> **username_3**: @domotorp make this into an answer? Possibly add http://people.seas.harvard.edu/~salil/pseudorandomness/  
> **username_3**: 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. https://en.wikipedia.org/wiki/Min-entropy  
> **username_0**: 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.  
> **username_1**: So the answer to my comment is “yes, I’m trying to feed a BPP algorithm with a nonuniform source of randomness”?  
> **username_1**: Are you aware of the existence of randomness extractors (see e.g. https://cs.haifa.ac.il/~ronen/online_papers/ICALPinvited.pdf)? Basically, a random source with min-entropy $k$ is not much different from a uniform $k$-bit source.  
> **username_0**: @Emil, the answer is I don't care either way, they're equivalent and you can answer in terms of bit lengths if you'd like.  

---

## 0 answers

