Why is randomness a problem? (i.e. why do we care about derandomization?)

Question

I'm reading Aaronson's survey on P vs. NP, and I've come to understand that in CS theory, people really care about derandomization results like P vs. BPP etc. My question is, what's the problem with randomness? If your algorithm is known to only require a polynomial number of random bits, then simply go ask a physicist to get the bits for you, which isn't a problem since you only need a tractable number of them, and then write them on the Turing machine tape and you're good! The goal of complexity theory is to figure out what we can compute in this universe, right? Well, this universe has randomness, right? So why do we care about derandomization? Theoretical and practical answers are both welcome.

Answer 1

Complexity theory is a mathematical theory which aims at addressing one shortcoming of computability theory, namely, it takes into account the use of resources. While it is true that in its early days it aimed to capture the notion of "practical computation" (even particular flavors such as parallel computation, supposedly captured by NC), it has since drifted apart and taken off from reality. As an example you can take higher steps on the polynomial hierarchy, higher complexity classes such as PSPACE, classes defined using alternation, and so on. Indeed, much of this material dates to the early days of complexity theory, showing that it lost touch with reality quite quickly.

Traditionally the two most important resources studied by complexity theory are time and space. However, other resources have also interested complexity theorists, for example alternation and randomness (not to mention the world of circuit complexity). Philosophically speaking, it is a fascinating question whether randomness dramatically reduces the computation time of some problems, or whether the gain is only polynomial (as hinted by the conjecture P=BPP). However, it does not seem to have any practical relevance, though not for the reason you mention. In practice there is no need for actual physical randomness (other than for cryptographic purposes), and pseudorandom number generators work well enough.

Answer 2

I'm not a complexity theory specialist, but I think there are somewhat practical reasons to be interested in this question.

1. As noted by Derek Elkins, actually producing "physical" random numbers is quite difficult, and producing the right distribution with the right amount of entropy at sufficient speed is hard enough to justify web sites and custom hardware. It would be nice to know this can be avoided, at least in theory.

2. In classical physics, there is no "true" randomness, just the (deterministic) physical laws and the initial conditions of the system (or the whole universe, I guess). It's an interesting philosophical question whether this randomness is equivalent to true randomness in some sense. This question finds answers in the fields of chaos theory, the theory of ergodic processes and in computer science, in questions like P vs BPP.

3. The question of whether we can accurately simulate randomness in P vs BPP seems very related to the question of whether we can truly do encryption, say, the existence of trapdoor or one-way functions. In particular, the ability to deterministically produce bits that "look random" enough for any particular algorithm seems like a good prerequisite to finding a cryptographic function which encrypts a given message into a stream of bits indistinguishable from random bits, if the key is not known. So solving the very hard question of existence of one-way functions should require solving P vs BPP along the way.