Butterflies And Complexity Theories
Meet the two types of complexity theory
Ray Bradbury is one of the great science fiction writers of all time. He is known for countless stories, short and long, many of which have become part of the fabric of our culture. Bradbury’s classic Fahrenheit 451 became a major motion picture starring Julie Christie and Oskar Werner; many of his other stories are also the basis of television shows and films.
Today I plan on talking about the other meaning of complexity theory, not computational complexity. It is related directly to one of Bradbury’s stories.
The story is his science fiction short story called “A Sound of Thunder.” It was published in Collier’s magazine in 1952 and has been re-published many times since then. As far as I can tell it introduced the name, the butterfly effect, that has been used to describe chaotic behavior.
Collier’s magazine was published from 1888 to 1957: the last issue was dated January 4, 1957. It is gone now. With all the changes occurring in publishing today, I wonder if we will have to explain that there once was a magazine called “Time.” Or even worse that we will have to explain what a “magazine” was?
The word “complexity” means two things, at least, in mathematics. The one used here, in GLL, is the cost of a computation: a problem has high complexity if the amount of some resource needed to solve the problem is large. The problem is a classic example, as are the Traveling Salesman Problem, and integer factoring—all are believed to be problems with high complexity.
The one used elsewhere is the behavior of a system: a system has high complexity if the system’s behavior—its evolution over time—is extremely difficult to predict. The weather is a classic example, as are turbulent airflow, and social systems—all are believed to be problems with high complexity.
In order to tell them apart the first is usually called computational complexity and the latter just complexity. I wish we had the term all by ourselves, but we have to share “complexity” unfortunately with others. The term by itself is so neat and descriptive. Oh well.
Chaos—An Informal Definition
One of the fundamental concepts in complexity of behavior theory (CBT) is the notion of chaos. This notion is traceable back to Henri Poincaré’s famous prize winning paper on the many-body problem. Informally a system that evolves is chaotic if it is unpredictable: The behavior must be sensitive to the initial condition—small changes should cause large changes in future behavior. Thus a mapping from a vector to where is a unitary matrix will not be chaotic: if is replaced by , then
As long as is small, the future state will not be far from the unperturbed state, since
does not grow in size as . Note that the formal definition of chaotic behavior usually includes additional conditions.
In “A Sound of Thunder” Bradbury introduced the notion of the butterfly effect. The short version of the story is simple: time travelers go back to the days of the dinosaurs, and when they return to the present, things are almost the same but not quite. They eventually discover that one of the travelers has a dead butterfly on his boot—the slight change to the past somehow rippled and changed the future. Since his story there have been several other stories and films based on exactly this simple notion. Clearly, in a dramatic way Bradbury is saying that the future is chaotic: even the removal of a single butterfly could somehow change the future.
Later Edward Lorenz, one of founders of CBT, was invited to give a talk at the AAAS meeting in 1972. Since he did not supply a title in time the chair created one:
Does the flap of a butterfly’s wings in Brazil set off a tornado in Texas?
Indeed does it?
Chaos—A Provable Example
The story of the term chaos as applied by CBT is itself a bit chaotic—perhaps that is to be expected. It was one of those cases where a beautiful paper proved a special case, then it was discovered that an earlier paper had proved the general case. Luckily there is plenty of credit to share.
Let’s look at it in the reverse order that it happened from an observer in the West. Tien-Yien Li and James Yorke wrote an engaging account of a beautiful theorem in their 1975 paper in the American Mathematical Monthly titled “Period Three Implies Chaos.” They proved:
Theorem: Let where is an interval and is a continuous function. If has a fixed point of period then it has one of all orders.
Note that a fixed point of order is a point so that
I believe they also were the first to use chaos in a technical way—now there are much more formal notions. Keith Burns and Boris Hasselblatt have said in a paper on chaos:
This theorem amazed the mathematical community.
Burns and Hasselblatt further give the story of how Aleksandr Sharkovsky’s work became known in the West: Some time after the publication of his paper Yorke attended a conference in East Berlin, during which a Ukrainian participant approached him. Although they had no language in common, Sharkovsky (for it was he) managed to convey that unbeknownst to Li and Yorke (and most of Western mathematics) he had proved his results about periodic points of interval mappings well before.
Indeed in 1964, Sharkovsky had introduced the following ordering on the positive integers:
He then proved:
Theorem: Let where is an interval and is a continuous function. If has a period point of order , then it also has a point of period length for any such that in this ordering.
This includes as a special case the great result of Li and Yorke. Thus if has a periodic point of order it has all orders except possibly . The importance of this result is it shows that simple maps can have very complex behavior. A map with many different points, with many different periods, has a chaotic type behavior.
This happens in mathematics more than I would have guessed: a special case is proved after the general case has been proved.
What Is The Complexity of Complexity?
Mark Braverman has worked on CBT, for his Ph.D. thesis. Since then he has gone in new directions and solved some terrific problems. One of the questions that we have discussed is what is really the complexity of predicting where a chaotic map will be. Let me explain. Suppose that is a map that exhibits chaotic behavior. Then it should be the case that predicting where will be after applications of is hard. But I do not see why this is the case, and I know of no complexity theorem—in our sense—that proves this. For example, can we prove:
Theorem? Let map to over the complex numbers, where are constants. Start at some point , and define
for . Any algorithm that can determine a so that
must take computational time .
What is the best we can do for ? Just because the mapping is chaotic does not imply that locating where the point is approximately is computationally hard. I asked Mark this exact question, and it appears to be conventional wisdom that it must be hard. But that is not a proof. Even if it is hard, what is the best upper bound? And what are special cases that are easy?
On the side, we can mention also a paper by Sam Buss, Christos Papadimitriou, and John Tsitsiklis, titled “On the predictability of coupled automata: an allegory about chaos.” It appeared in FOCS 1991 and then was published in the journal Complex Systems, thus getting the attention of both kinds of complexity people. The paper is on sets of identical finite automata that are coupled in the sense that the next 0-or-1 input for all of them depends on a first-order expressible property of their current states. The problem is, given an -tuple of starting states and a time in binary, predict the states after steps. They show a sharp dichotomy that the problem is in or is -complete according to whether the property is invariant under permutations of the (names of the) states. Thus again, the complexity of complexity is open.
I have raised some open questions already. Just want to announce that this post is number . We will not hit another power of for some time. Wikipedia points out that has many cool properties which prompts us to mention:
- Ryan Williams’ hometown area code in Alabama.
- The number of NFL regular season football games.
- The number used by short track speed skating Olympian Apolo Ohno.