6
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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 $\endgroup$ Commented Sep 22, 2023 at 4:15
  • $\begingroup$ 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. $\endgroup$ Commented Sep 22, 2023 at 6:04
  • $\begingroup$ 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... $\endgroup$ Commented Sep 23, 2023 at 22:05
  • $\begingroup$ @Jason Gaitonde So NEXPTIME could be tractable? $\endgroup$ Commented Sep 23, 2023 at 22:07
  • $\begingroup$ @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. $\endgroup$ Commented Sep 23, 2023 at 22:14

2 Answers 2

6
$\begingroup$

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 that "a lot of cryptography collapses."

$\endgroup$
8
  • $\begingroup$ 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? $\endgroup$ Commented Sep 22, 2023 at 16:14
  • $\begingroup$ (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.) $\endgroup$ Commented Sep 22, 2023 at 16:18
  • 1
    $\begingroup$ @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. $\endgroup$ Commented Sep 22, 2023 at 17:27
  • $\begingroup$ 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. $\endgroup$ Commented Sep 22, 2023 at 17:51
  • 2
    $\begingroup$ @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. $\endgroup$ Commented Sep 22, 2023 at 18:13
1
$\begingroup$

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.

$\endgroup$
7
  • 4
    $\begingroup$ I don't think how well believed something is all that related to how hard it is to prove $\endgroup$ Commented Sep 24, 2023 at 6:04
  • $\begingroup$ @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$. $\endgroup$ Commented Sep 24, 2023 at 15:41
  • $\begingroup$ 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. $\endgroup$ Commented Sep 25, 2023 at 2:39
  • $\begingroup$ @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). $\endgroup$ Commented Sep 25, 2023 at 3:41
  • 1
    $\begingroup$ @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. $\endgroup$ Commented Sep 27, 2023 at 16:59

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.