Facebook
Reddit
Discord Invitation
)Meet the two types of complexity theory
by R. Lipton
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?
Complexity
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 SAT 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 tor
As long as
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
Note that a fixed point of order
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
This includes as a special case the great result of Li and Yorke. Thus if
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
Theorem? Let
must take computational time
What is the best we can do for
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
Open Problems
I have raised some open questions already. Just want to announce that this post is number 256. We will not hit another power of 2 for some time. Wikipedia points out that 256 has many cool properties which prompts us to mention:
1. Ryan Williams’ hometown area code in Alabama.
2. The number of NFL regular season football games.
3. The number used by short track speed skating Olympian Apolo Ohno.
Source
