Focus: Complexity is Elusive

Phys. Rev. Focus 13, 10
Some problems that seem to require computer crunching aren’t so hard if you only need approximate answers.
Emerging complexity. In this simulation of a cellular automaton, each row of pixels is derived from the one above it by following a simple rule. Although the precise arrangement on a given row is unpredictable without running the program, an approximate answer can sometimes be calculated in advance. (Click image for an expanded version.)Emerging complexity. In this simulation of a cellular automaton, each row of pixels is derived from the one above it by following a simple rule. Although the precise arrangement on a given row is unpredictable without running the program, an approxim... Show more

Researchers need enormous computer power to forecast changes in the Earth’s climate, but they can predict the speed of a ball rolling down a ramp with pencil and paper. Stephen Wolfram claimed in his 2002 best seller, A New Kind of Science, that there is a clear dividing line between complex problems that require computer crunching and those for which equations alone will do. He argued that many important problems are more like the climate than the ball. But according to the 20 February PRL, his definition of complexity is imperfect because many of the problems he classified as complex are easily solved, as long as you can accept approximate answers. The results suggest that the traditional approach of physics–the equivalent of pencil and paper–is more widely applicable than Wolfram’s analysis implies.

Wolfram’s book describes checkerboard-like arrays of colored squares (“cells”), called cellular automata, which are generated by following simple rules. For example, the Game of Life, described in 1970 [1] follows the rule that if two or three of the neighbors of a black cell are currently black, it will remain black in the next update of the picture; if it is currently white, it will become black if it has three black neighbors. The rule runs over and over, continually changing the picture in surprisingly complex ways.

Many rules quickly settle into simple patterns, such as unchanging, oscillating, or random. But some rules generate complex patterns that are “computationally irreducible,” meaning there are no shortcuts to predict what they will do. Unlike electric circuits or cannon balls, you can’t find the result by plugging numbers into equations; you have to run the program to see what happens. Wolfram suggests that rules like these govern much of the natural world, such as the climate or highway traffic, so precise mathematical predictions are impossible for most of the important phenomena.

“It is tempting to conclude from this that the enterprise of physics is doomed from the outset,” write Navot Israeli and Nigel Goldenfeld, of the University of Illinois at Urbana-Champaign. But precise predictions aren’t always necessary. For example, the temperature and pressure of a gas can be accurately described without knowing about the motion of every molecule. “We tried to see what would happen if you asked only approximate questions,” says Goldenfeld.

So Israeli and Goldenfeld sought ways to replace several cells of an automaton with a single cell, “fuzzing out” the details of the picture–like making a low-resolution digital image from a higher-resolution version. The team also devised a new rule for the low-resolution automaton that would lead to the same long-term behavior as the original automaton if it were fuzzed at the end.

The researchers found that for some rules, the low-res version behaved simply and predictably, even when the high-res version was computationally irreducible and therefore unpredictable. In other words, the complexity was only in the unimportant details. Goldenfeld concludes that if you only need approximate results, they are predictable in many complex problems, and “computational irreducibility is not the right way to measure complexity.”

Wolfram says the “nice, small paper” is useful, if not very surprising. The interesting issue, he says, is “under what circumstances will large-scale rules emerge” that allow a simple, predictable description of a complex phenomenon.

–Don Monroe

Don Monroe is a freelance science writer in Murray Hill, New Jersey.


  1. M. Gardner, Scientific American 223, 120 (October 1970); Martin Gardner’s “Mathematical Games” column described the Game of Life, invented by John Horton Conway of the University of Cambridge, UK.

More Information

Subject Areas

Complex Systems

Related Articles

Focus: How to Compare Books or Genomes
Complex Systems

Focus: How to Compare Books or Genomes

A mathematical technique for comparing large symbol sets suggests that less frequently used words are mainly responsible for the evolution of the English language over the past two centuries. Read More »

Focus: Wikipedia Articles Separate into Four Categories
Interdisciplinary Physics

Focus: Wikipedia Articles Separate into Four Categories

A study of the entire editing history of English Wikipedia shows that the articles cluster into four categories based on how frequently and how aggressively they are edited. Read More »

Synopsis: Fractal London
Statistical Physics

Synopsis: Fractal London

An analysis of London’s street network shows how the network has evolved over time from a heterogeneous to homogeneous fractal pattern. Read More »

More Articles