<p>To me, the intuitive reason for believing that <span class="math-container">$BPP = P$</span> is that if you describe to me a randomized algorithm, then in practice, I can implement it by using a pseudorandom number generator (PRNG) instead of a &quot;true&quot; random number generator (RNG).</p>
<p>If <span class="math-container">$BPP \ne P$</span>, then that means that there's a problem that you can always solve with a &quot;true&quot; source of randomness, but that for any PRNG you might try, there's an instance of the problem that defeats the PRNG.  While we can't rule out this possibility rigorously, it would mean that the problem somehow encodes a &quot;universal&quot; way to distinguish an arbitrary PRNG from a true RNG, including so-called &quot;cryptographically secure&quot; PRNGs.  This is what is meant by <a href="https://cstheory.stackexchange.com/questions/53339/what-are-the-consequences-of-bpp-neq-p#comment118458_53339">Command Master's comment</a> that &quot;a lot of cryptography collapses.&quot;</p>

CC BY-SA 4.0
2023-09-22T16:14:17.693Z
Even if PRNGS are always secure, you would need something to seed the PRNG, would you not? And if you just use the input, what happens if the value chosen happens to be sub-optimal? Also, even if BPP = P, would it still be on the table that randomized algorithms give polynomial Speedups? Because I would hardly call an O(n^100) deterministic algorithm for a problem that can be solved in O(n^2) by a randomized one. But just because an algorithm has a lot of complicated moving parts, to me, does not imply it's random. Also, I know BPP vs EXP is open, how does that relate?
Colonizor48
CC BY-SA 4.0
2023-09-22T16:18:40.343Z
(Though, even I, someone who still thinks P = NP isn't totally impossible, would find BPP containing EXP to be a bit much, but a welcome surprise with how much power we would get from exp-time being tractable.)
Colonizor48
CC BY-SA 4.0
2023-09-22T17:27:58.243Z
@Colonizor48 You're correct. We're talking only about intuition. It's highly unintuitive to most people that if we let the seed be a cryptographic hash of the input, there would still be plenty of instances where the PRNG would still behave superpolynomially worse than the true RNG. But if that doesn't sound unintuitive to you, then there's not much more one can say in this direction. By the way, this line of thinking is what lies behind many of the rigorous results on the $BPP = P$ question.
Timothy Chow
CC BY-SA 4.0
2023-09-22T17:51:01.340Z
Fair enough, though again, too me just because something *seems* random doesn't mean there is no structure. Though how exploitable said structure is is a topic for another time. Which is one of the reasons I believe we can't rule out P = NP to easily. Even if the algorithm is an O(n^10) algorithm with a large constant. And you would have to consider all possible algorithms, including all of the ones that are 100 terabytes long, and seemingly sometimes solve SAT in O(n^2), but that we cannot prove if it halts on most instances, but if it does then it solves SAT in O(n^10000) in the worst case.
Colonizor48
CC BY-SA 4.0
2023-09-22T18:13:41.180Z
@Colonizor48 Again you are correct, except that I would say that "how exploitable said structure is" is not a topic for another time, but precisely the current topic. A problem in $BPP$ but not $P$ would in effect be exploiting the structure in the PRNG to distinguish it from true random. If you study a little cryptography, you'll find that exploiting cryptographic weaknesses is, at its core, the task of distinguishing pseudorandom from random. Once you can do that, you can usually parlay that into a full-fledged cryptanalytic attack.
Timothy Chow
CC BY-SA 4.0
2023-09-22T18:49:23.273Z
That is a good point, though I would like to bring up a few others. 1, you could perhaps diagonalize over all possible PRNGs to construct a problem in BPP but not in P, that runs in superpolytime on all inputs w/out true random. 2. on the specific definition of BPP, the constant 1/3 error seems somewhat arbitrary, and in my view, there is no good reason for P to equal BPP exactly due to this, though I could be misunderstanding something. 3. just because in theory BPP != P is true, does not necessarily mean there are any practical attacks on cryptography. Again, PRNG could be O(n^100) to break.
Colonizor48
CC BY-SA 4.0
2023-09-22T18:51:23.533Z
Also, BPP !=P would imply that PP !=P, which would be a pretty big step forward, though I am one to avoid arguments based on how "Nicely" they fit with current knowledge. Math is not science. And math has proven us wrong before. Speaking of which, how does all of this relate to PP?
Colonizor48
CC BY-SA 4.0
2023-09-23T02:22:15.267Z
@Colonizor48 1. This doesn't seem likely, although I can't really see what you're suggesting. 2. The constant is indeed arbitrary — if you replace it by $\frac1{2^{n^{10}}}$ you get exactly the same language class, because given an algorithm if you repeat it enough times and take the majority you get that error. 3. Theoretical cryptography usually assumes the impossibility of any polynomial attack, so while it's possible such an attack wouldn't be practical it would still affect theoretical cryptography significantly.
Command Master
CC BY-SA 4.0
2024-07-06T02:32:10.800Z
This is a good answer. I agree that PRNG's are probably good enough for most problems, and maybe there's some PRNG that's good enough for *all* problems. What has never made sense to me: when we are talking about $BPP$, we are talking about the situation where the algorithm is only required to give the right answer, let's say, 51% of the time. I am sure we can use a PRNG to build a corresponding algorithm in P that gives the right answer only 51% of instances. But if you want it in P, you still have to turn it into an algorithm that is *always* right! How do you do that? (1/2)
Mike Battaglia
CC BY-SA 4.0
2024-07-06T02:33:35.387Z
Given that, the intuitive idea that "PRNG = RNG" has always seemed neither here nor there to me when deciding P = BPP. it seems like even if "PRNG = RNG" is true, which it very well could be, it would have no bearing on P = BPP at all, for this reason. On the other hand, I have no problem believing that, let's call it $P_{\text{only right for 51% of instances}} = BPP$. (2/2)
Mike Battaglia
CC BY-SA 4.0
2024-07-06T12:53:41.673Z
@MikeBattaglia You're right that to deduce $\mathsf{P}=\mathsf{BPP}$, we need to assume a little more; we need to assume something like, "$\mathsf{E}$ contains problems with exponential circuit complexity." This is the famous result of Impagliazzo and Wigderson; see for example Corollary 7.64 [here](https://web.archive.org/web/20240421101755/https://people.seas.harvard.edu/~salil/pseudorandomness/pseudorandomness-Aug12.pdf). But still, the idea of the proof is to simulate an RNG with a PRNG. It's just that with the hardness assumption, the simulation can be polynomial rather than exponential.
Timothy Chow
CC BY-SA 4.0
2024-07-06T23:46:43.137Z
OK, I don't quite get how it follows, but this seems interesting enough to be its own question, which I posted here: https://cstheory.stackexchange.com/questions/54469/why-would-the-existence-of-a-sufficiently-strong-prng-prove-p-bpp
Mike Battaglia
CC BY-SA 4.0
2023-09-22T15:56:03.720Z
2023-09-22T15:56:03.720Z
Timothy Chow
<p>I think, the main reason for most researchers to prefer the <span class="math-container">$BPP=P$</span> conjecture over <span class="math-container">$BPP\neq P$</span> is that there is a very strong asymmetry in their perceived difficulty. Specifically,</p>
<p>(1) <span class="math-container">$BPP\neq P$</span> implies <span class="math-container">$P\neq NP$</span>, so proving <span class="math-container">$BPP\neq P$</span> is as hard as proving <span class="math-container">$P\neq NP$</span>. As such, it offers extremely little chance for success.</p>
<p>(2) Proving <span class="math-container">$BPP=P$</span> offers much more chance. For this, it is enough to find an appropriate PRNG that works for every <span class="math-container">$BPP$</span> problem. Given the already known sophisticated PRNG constructions that work in most cases, it seems quite conceivable that a possibly small further improvement may do the trick.</p>
<p>Therefore, proving <span class="math-container">$BPP=P$</span> appears much more doable than proving <span class="math-container">$BPP\neq P$</span>. Not surprisingly, the more doable possibility also seems more realistic. Of course, this does not prove anything, but explains why most people prefer the <span class="math-container">$BPP=P$</span> conjecture.</p>

CC BY-SA 4.0
2023-09-24T06:04:43.117Z
I don't think how well believed something is all that related to how hard it is to prove
Command Master
CC BY-SA 4.0
2023-09-24T15:41:56.947Z
@CommandMaster In principle, you may be right. However, if a claim appears incomparably  easier to prove than to disprove, this can serve as a good reason to believe that the claim is probably true. Here the claim is $BPP=P$. The history of the problem also supports this. The original consensus on $BPP\neq P$ shifted to its negation after the Nisan-Wigderson PRNG was published, giving a real chance to prove  $BPP=P$.
Andras Farago
CC BY-SA 4.0
2023-09-25T02:39:44.930Z
Well, proving P = BPP is gonna be a whole hell of a lot easier then P not equal to BPP if P = NP.(Unless ZFC is inconsistent) Truth does not depend on how hard something is to prove.
Colonizor48
CC BY-SA 4.0
2023-09-25T03:41:27.693Z
@Colonizor48 I agree that the truth does not depend on proof hardness. However, in this case we do not know the truth. Therefore, we can only make guesses about how  realistic/likely each possibility is. It is not unreasonable to say that the option that promises a much easier proof is probably more realistic. In this sense, while perceived proof hardness cannot not separate true or false, it can still help separating the likely true from the likely false (as long as we do not know the actual truth).
Andras Farago
CC BY-SA 4.0
2023-09-27T12:21:18.560Z
@AndrasFarago It is unknown whether [a square can be dissected into an equilateral triangle using only 3 pieces](https://mathoverflow.net/a/455352). If it can be, the proof will be straightforward: just exhibit the dissection. If it cannot, then the proof will require a genuinely new idea that nobody has thought of to date. Does this mean that the option that promises a much easier proof is probably more realistic? Nobody believes that. In fact, the option with an easier proof is *less* realistic, because if it were easy then someone would probably have found it by now.
Timothy Chow
CC BY-SA 4.0
2023-09-27T16:59:15.627Z
@TimothyChow I think, your argument confuses the structural simplicity of the proof with the easiness of finding the proof. For example, in this sense it would be much easier to prove that a SAT formula is satisfiable than not. For proving satisfiability just exhibit a satisfying truth assignment. Proving non-satisfiability  may be much harder (unless NP=co-NP). However, the easiness of exhibiting a satisfying truth assignment (once found) does not mean at all that it is also easy to find it.
Andras Farago
CC BY-SA 4.0
2023-09-27T19:29:51.880Z
@AndrasFarago Okay, so you're claiming that we're quite close to actually proving $BPP=P$. Yes? It doesn't seem to me that we're particularly close, but of course that's a matter of opinion. I think you confused everyone by trying to make some general statement about the relationship between easy proofs and truth. The general statement you're making sounds manifestly false to me, but that's getting off topic.
Timothy Chow
CC BY-SA 4.0
2023-09-24T04:56:09.907Z
2023-09-24T04:56:09.907Z
Andras Farago
<p>I have seen a lot of people assume, <span class="math-container">$BPP = P$</span> . But to me, this seems false intuitively.(Though math is not without unintuitive results) And, to my admittedly limited understanding of the topic, the evidence I have seen does not seem that strong frankly. I know that <span class="math-container">$BPP \neq P$</span> implies <span class="math-container">$E$</span> has sub-exponential circuits. What are some other consequences of <span class="math-container">$BPP \neq P$</span>? I know that would trivially mean <span class="math-container">$P \neq PP$</span> as well.</p>

CC BY-SA 4.0
2023-09-22T04:15:39.723Z
A fairly commonly used notation abuse of $\text{BPP} = \text{P}$ is that for each $BPP$ language $A$ there's a $P$ language $B$ such that it's hard (not polynomial) to find elements in $A \oplus B$. This weaker result is implied by the existence of cryptographically secure randomness, so if it is wrong then a lot of cryptography collapses. Even the stronger $BPP = P$ result is believed to be implied by sufficiently strong pseudorandom generators
Command Master
CC BY-SA 4.0
2023-09-22T06:04:48.297Z
BPP $\ne$ P does *not* imply that E has polynomial circuits, only that it has circuits of size $2^{o(n)}$ for infinitely many input lengths.
Emil Jeřábek
CC BY-SA 4.0
2023-09-23T22:05:22.853Z
Some clarifying points: (1) good PRGs (with $C\log n$ seed, so one can brute force) exist to derandomize BPP, the question is whether one is *efficient*. (2) Under certain hardness assumptions, derandomization incurs just a factor of basically $n$ overhead, and there's some evidence this is unavoidable. I'm not an expert though, see e.g. work of Lijie Chen for more info. (3) BPP vs even NEXP is indeed still open and actually holds relative to some oracle. Relatedly, this means one likely can't naively do diagonalization since P vs BPP does not relativize. (4) BPP != P also implies P != NP...
Jason Gaitonde
CC BY-SA 4.0
2023-09-23T22:07:11.140Z
@Jason Gaitonde So NEXPTIME *could* be tractable?
Colonizor48
CC BY-SA 4.0
2023-09-23T22:14:08.210Z
@Colonizor48 In the sense that there exists a (very artificial and powerful) oracle where randomness becomes this computationally useful, yes. But it's fair to say basically nobody believes this is the case in the actual (non-oracle) world.
Jason Gaitonde
<polynomial-time><derandomization><probabilistic-computation>
What are the consequences of $BPP \neq P$?
Colonizor48
# What are the consequences of $BPP \neq P$?

(Asked by: username_0 on 2023-09-21)

I have seen a lot of people assume, $BPP = P$ . But to me, this seems false intuitively.(Though math is not without unintuitive results) And, to my admittedly limited understanding of the topic, the evidence I have seen does not seem that strong frankly. I know that $BPP \neq P$ implies $E$ has sub-exponential circuits. What are some other consequences of $BPP \neq P$? I know that would trivially mean $P \neq PP$ as well.

**Tags:** polynomial-time, derandomization, probabilistic-computation
> **Comments:**
> **username_1**: A fairly commonly used notation abuse of $\text{BPP} = \text{P}$ is that for each $BPP$ language $A$ there's a $P$ language $B$ such that it's hard (not polynomial) to find elements in $A \oplus B$. This weaker result is implied by the existence of cryptographically secure randomness, so if it is wrong then a lot of cryptography collapses. Even the stronger $BPP = P$ result is believed to be implied by sufficiently strong pseudorandom generators  
> **username_2**: BPP $\ne$ P does *not* imply that E has polynomial circuits, only that it has circuits of size $2^{o(n)}$ for infinitely many input lengths.  
> **username_3**: Some clarifying points: (1) good PRGs (with $C\log n$ seed, so one can brute force) exist to derandomize BPP, the question is whether one is *efficient*. (2) Under certain hardness assumptions, derandomization incurs just a factor of basically $n$ overhead, and there's some evidence this is unavoidable. I'm not an expert though, see e.g. work of Lijie Chen for more info. (3) BPP vs even NEXP is indeed still open and actually holds relative to some oracle. Relatedly, this means one likely can't naively do diagonalization since P vs BPP does not relativize. (4) BPP != P also implies P != NP...  
> **username_0**: @Jason Gaitonde So NEXPTIME *could* be tractable?  
> **username_3**: @Colonizor48 In the sense that there exists a (very artificial and powerful) oracle where randomness becomes this computationally useful, yes. But it's fair to say basically nobody believes this is the case in the actual (non-oracle) world.  

---

## 2 answers

### Answer by username_4 on 2023-09-22. Score: 6 | Accepted answer

To me, the intuitive reason for believing that $BPP = P$ is that if you describe to me a randomized algorithm, then in practice, I can implement it by using a pseudorandom number generator (PRNG) instead of a "true" random number generator (RNG).

If $BPP \ne P$, then that means that there's a problem that you can always solve with a "true" source of randomness, but that for any PRNG you might try, there's an instance of the problem that defeats the PRNG. While we can't rule out this possibility rigorously, it would mean that the problem somehow encodes a "universal" way to distinguish an arbitrary PRNG from a true RNG, including so-called "cryptographically secure" PRNGs. This is what is meant by [Command Master's comment](https://cstheory.stackexchange.com/questions/53339/what-are-the-consequences-of-bpp-neq-p#comment118458_53339) that "a lot of cryptography collapses."

> **Comments:**
> **username_0**: Even if PRNGS are always secure, you would need something to seed the PRNG, would you not? And if you just use the input, what happens if the value chosen happens to be sub-optimal? Also, even if BPP = P, would it still be on the table that randomized algorithms give polynomial Speedups? Because I would hardly call an O(n^100) deterministic algorithm for a problem that can be solved in O(n^2) by a randomized one. But just because an algorithm has a lot of complicated moving parts, to me, does not imply it's random. Also, I know BPP vs EXP is open, how does that relate?  
> **username_0**: (Though, even I, someone who still thinks P = NP isn't totally impossible, would find BPP containing EXP to be a bit much, but a welcome surprise with how much power we would get from exp-time being tractable.)  
> **username_4**: @Colonizor48 You're correct. We're talking only about intuition. It's highly unintuitive to most people that if we let the seed be a cryptographic hash of the input, there would still be plenty of instances where the PRNG would still behave superpolynomially worse than the true RNG. But if that doesn't sound unintuitive to you, then there's not much more one can say in this direction. By the way, this line of thinking is what lies behind many of the rigorous results on the $BPP = P$ question.  
> **username_0**: Fair enough, though again, too me just because something *seems* random doesn't mean there is no structure. Though how exploitable said structure is is a topic for another time. Which is one of the reasons I believe we can't rule out P = NP to easily. Even if the algorithm is an O(n^10) algorithm with a large constant. And you would have to consider all possible algorithms, including all of the ones that are 100 terabytes long, and seemingly sometimes solve SAT in O(n^2), but that we cannot prove if it halts on most instances, but if it does then it solves SAT in O(n^10000) in the worst case.  
> **username_4**: @Colonizor48 Again you are correct, except that I would say that "how exploitable said structure is" is not a topic for another time, but precisely the current topic. A problem in $BPP$ but not $P$ would in effect be exploiting the structure in the PRNG to distinguish it from true random. If you study a little cryptography, you'll find that exploiting cryptographic weaknesses is, at its core, the task of distinguishing pseudorandom from random. Once you can do that, you can usually parlay that into a full-fledged cryptanalytic attack.  
> **username_0**: That is a good point, though I would like to bring up a few others. 1, you could perhaps diagonalize over all possible PRNGs to construct a problem in BPP but not in P, that runs in superpolytime on all inputs w/out true random. 2. on the specific definition of BPP, the constant 1/3 error seems somewhat arbitrary, and in my view, there is no good reason for P to equal BPP exactly due to this, though I could be misunderstanding something. 3. just because in theory BPP != P is true, does not necessarily mean there are any practical attacks on cryptography. Again, PRNG could be O(n^100) to break.  
> **username_0**: Also, BPP !=P would imply that PP !=P, which would be a pretty big step forward, though I am one to avoid arguments based on how "Nicely" they fit with current knowledge. Math is not science. And math has proven us wrong before. Speaking of which, how does all of this relate to PP?  
> **username_1**: @Colonizor48 1. This doesn't seem likely, although I can't really see what you're suggesting. 2. The constant is indeed arbitrary — if you replace it by $\frac1{2^{n^{10}}}$ you get exactly the same language class, because given an algorithm if you repeat it enough times and take the majority you get that error. 3. Theoretical cryptography usually assumes the impossibility of any polynomial attack, so while it's possible such an attack wouldn't be practical it would still affect theoretical cryptography significantly.  
> **username_5**: This is a good answer. I agree that PRNG's are probably good enough for most problems, and maybe there's some PRNG that's good enough for *all* problems. What has never made sense to me: when we are talking about $BPP$, we are talking about the situation where the algorithm is only required to give the right answer, let's say, 51% of the time. I am sure we can use a PRNG to build a corresponding algorithm in P that gives the right answer only 51% of instances. But if you want it in P, you still have to turn it into an algorithm that is *always* right! How do you do that? (1/2)  
> **username_5**: Given that, the intuitive idea that "PRNG = RNG" has always seemed neither here nor there to me when deciding P = BPP. it seems like even if "PRNG = RNG" is true, which it very well could be, it would have no bearing on P = BPP at all, for this reason. On the other hand, I have no problem believing that, let's call it $P_{\text{only right for 51% of instances}} = BPP$. (2/2)  
> **username_4**: @MikeBattaglia You're right that to deduce $\mathsf{P}=\mathsf{BPP}$, we need to assume a little more; we need to assume something like, "$\mathsf{E}$ contains problems with exponential circuit complexity." This is the famous result of Impagliazzo and Wigderson; see for example Corollary 7.64 [here](https://web.archive.org/web/20240421101755/https://people.seas.harvard.edu/~salil/pseudorandomness/pseudorandomness-Aug12.pdf). But still, the idea of the proof is to simulate an RNG with a PRNG. It's just that with the hardness assumption, the simulation can be polynomial rather than exponential.  
> **username_5**: OK, I don't quite get how it follows, but this seems interesting enough to be its own question, which I posted here: https://cstheory.stackexchange.com/questions/54469/why-would-the-existence-of-a-sufficiently-strong-prng-prove-p-bpp  

---

### Answer by username_6 on 2023-09-24. Score: 1

I think, the main reason for most researchers to prefer the $BPP=P$ conjecture over $BPP\neq P$ is that there is a very strong asymmetry in their perceived difficulty. Specifically,

(1) $BPP\neq P$ implies $P\neq NP$, so proving $BPP\neq P$ is as hard as proving $P\neq NP$. As such, it offers extremely little chance for success.

(2) Proving $BPP=P$ offers much more chance. For this, it is enough to find an appropriate PRNG that works for every $BPP$ problem. Given the already known sophisticated PRNG constructions that work in most cases, it seems quite conceivable that a possibly small further improvement may do the trick.

Therefore, proving $BPP=P$ appears much more doable than proving $BPP\neq P$. Not surprisingly, the more doable possibility also seems more realistic. Of course, this does not prove anything, but explains why most people prefer the $BPP=P$ conjecture.

> **Comments:**
> **username_1**: I don't think how well believed something is all that related to how hard it is to prove  
> **username_6**: @CommandMaster In principle, you may be right. However, if a claim appears incomparably  easier to prove than to disprove, this can serve as a good reason to believe that the claim is probably true. Here the claim is $BPP=P$. The history of the problem also supports this. The original consensus on $BPP\neq P$ shifted to its negation after the Nisan-Wigderson PRNG was published, giving a real chance to prove  $BPP=P$.  
> **username_0**: Well, proving P = BPP is gonna be a whole hell of a lot easier then P not equal to BPP if P = NP.(Unless ZFC is inconsistent) Truth does not depend on how hard something is to prove.  
> **username_6**: @Colonizor48 I agree that the truth does not depend on proof hardness. However, in this case we do not know the truth. Therefore, we can only make guesses about how  realistic/likely each possibility is. It is not unreasonable to say that the option that promises a much easier proof is probably more realistic. In this sense, while perceived proof hardness cannot not separate true or false, it can still help separating the likely true from the likely false (as long as we do not know the actual truth).  
> **username_4**: @AndrasFarago It is unknown whether [a square can be dissected into an equilateral triangle using only 3 pieces](https://mathoverflow.net/a/455352). If it can be, the proof will be straightforward: just exhibit the dissection. If it cannot, then the proof will require a genuinely new idea that nobody has thought of to date. Does this mean that the option that promises a much easier proof is probably more realistic? Nobody believes that. In fact, the option with an easier proof is *less* realistic, because if it were easy then someone would probably have found it by now.  
> **username_6**: @TimothyChow I think, your argument confuses the structural simplicity of the proof with the easiness of finding the proof. For example, in this sense it would be much easier to prove that a SAT formula is satisfiable than not. For proving satisfiability just exhibit a satisfying truth assignment. Proving non-satisfiability  may be much harder (unless NP=co-NP). However, the easiness of exhibiting a satisfying truth assignment (once found) does not mean at all that it is also easy to find it.  
> **username_4**: @AndrasFarago Okay, so you're claiming that we're quite close to actually proving $BPP=P$. Yes? It doesn't seem to me that we're particularly close, but of course that's a matter of opinion. I think you confused everyone by trying to make some general statement about the relationship between easy proofs and truth. The general statement you're making sounds manifestly false to me, but that's getting off topic.  

---

