7
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I would add, though, that practically speaking in those cases "true" randomness is needed, it is actually useful to minimize it, as collecting entropy is relatively slow. $\endgroup$
    – Derek Elkins left SE
    Jan 29, 2017 at 10:35
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 1. Doesn't random.org actually demonstrate that producing physical random numbers is so fast that one guy is able to make enough of them to supply the whole internet? 2. Our current best model of atomic physics is quantum mechanics, which is intrinsically random. Classical physics can't even begin to explain things like black body radiation or the photoelectric effect. $\endgroup$
    – David Richerby
    Jan 31, 2017 at 19:55
  • $\begingroup$ @DavidRicherby: 1. the numbers suggest 165.2 gigabits over 9 years which doesn't seem like that much (certainly not enough for the whole internet, say if they were being used as nonces for crypto purposes). 2. I think the jury's still somewhat out for QM and "true randomness" (though afaik, QM does seem to be a source of purely probabilistic information). The question for classical mechanics is still of interest though, since as far as computing and "everyday" physics goes, we live in a classical world. $\endgroup$
    – cody
    Jan 31, 2017 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.