The traditional approach of mathematicians and computer scientists to complexity, the general theory of computational complexity, focuses on very general classes such as P and NP. In this book József Beck takes on the big subjects of randomness and complexity, but he has in mind a much different approach. He focuses instead on carefully chosen concrete examples. The overall objective of the book is to identify examples, supported by proofs, of the rather vague complexity law:
- Discrete systems are either “simple” or they exhibit “advanced pseudorandomness” with or without constraints (even when there is no apparent independence), and
- Roughly speaking, a priori probabilities often exist, even when there is no intrinsic symmetry.
Much of the book is devoted to the work of giving meaning and substance to this law. The result is unusual, idiosyncratic, and thoroughly intriguing.
The book is divided into three sections. The first is called “Reading the shadows on the wall and formulating a vague conjecture.” Beck begins by collecting data for “advanced pseudorandomness,” largely in number theory: prime numbers and the Riemann hypothesis, normal numbers and apparent randomness in digit sequences, and the 3n + 1 (or Collatz) conjecture, among others.
The Principle of Insufficient Reason is the major topic of one chapter. It states that if you have no grounds whatsoever for believing that any one of n mutually exclusive events is more likely to occur than any other, then you should assign a probability of 1/n to each. (For some arguments – in the realm of prime numbers, for example, a variation is necessary — equiprobability is replaced by probability 1/log n that a given n is a prime.) Massive computational evidence suggests the success of this principle in “proving” that √2 is a normal number, that the sequence (3/2)n is uniformly distributed modulo one, and that the 3n + 1 conjecture is true. While Beck can supply no support for the Principle of Insufficient Reason in number theory, he does so in the context of combinatorics and real game theory. These are the subjects of Parts 2 and 3 of the book.
The first section of the book would be entertaining reading for anyone with a decent background in undergraduate mathematics. The other two sections are aimed more at specialists. The third part, in particular, has new results about graph games. Beck says that his book is self-contained, and mostly it is, though it’s a wild ride. This is more monograph than textbook; it has no exercises. It also has no index and seriously needs one.
Bill Satzer (wjsatzer@mmm.com) is a senior intellectual property scientist at 3M Company, having previously been a lab manager at 3M for composites and electromagnetic materials. His training is in dynamical systems and particularly celestial mechanics; his current interests are broadly in applied mathematics and the teaching of mathematics.