Randomness and Nondeterminism
Leonid A. Levin · Birkhäuser Basel eBooks · 1995
Exponentiation makes the difference between the bit size of this line and the number (“ 2300) of particles in the known universe. The expulsion of exponential time algorithms from computer theory in the 1960s created a deep gap between deterministic computation and — formely its unremarkable tools — randomness and nondeterminism. These two “freedom” of computation preserved their reputation as some of the most mysterious phenomena in science and seem to play an ever more noticeable role in computer theory. We have learned little in the past decades about the power of either, but a vague pattern is emerging in their relationships.