[bodhiandphysics]

It's a little funny for me to say this (my shtick in my lab is that I used randomized algorithms for everything), but whether this is true is actually a major open problem in complexity theory. Many famous problems are polynomial using random algorithms (famously determining if a number is Prime, and min cut of a graph), but over the years poly time algorithms have been found for many of these situations. Most complexity theorists I find believe that the random complexity classes (ZPP, RP, and BPP) are probably just P (BQP, the quantum analog to BPP is almost certainly not P). That of course doesn't mean that randomization can't speed you up! Prime determination is O(n^6) deterministically but O(n^2) using random search, n being the number of bits.

[Ar-Curunir]

yup. To elaborate (informally) on why theorists believe BPP = P, basically if we believe cryptography and hence PRGs exist, then every algorithm can be derandomized.

[adgjlsfhk1]

How does this follow? I understand that PRNGs let you construct randomized algorithms in practice, but how do you transfer probably polynomial runtime to definitely polynomial runtime?

[ablob]

How does PRNG follow from cryptography?

[forty]

This a a good summary of the article ^^