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?
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 
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 
As long as 
does not grow in size 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
where
is an interval and
is a continuous function. If
then it has one of all orders.
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
, then it also has a point of period length
for any
in this ordering.
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
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 
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 
- 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.
Trackbacks
- Tweets that mention Butterflies And Complexity Theories « Gödel’s Lost Letter and P=NP -- Topsy.com
- Sightseeing « phknrocket1k
- This Statement Does Not Refer To Itself « Gödel’s Lost Letter and P=NP
- Whose Complexity Is It Anyway? « Gödel’s Lost Letter and P=NP
- Have you noticed a recent heat rash? | World's Only Rational Man
- What will trigger the next correction? | Above the Market
- Bear Territory | Above the Market
Very interesting post (and I’ll be coming back, I stumbled across your blog poking around for Watson-related stuff). I was not aware of Sharkovsky’s Theorem, and your description of the ordering of the positive integers left me wondering, “Why is that particular ordering useful, and where are all the powers of 2?” I did some digging, and found a paper that offers a “natural, direct” proof at http://math.arizona.edu/~dwang/BurnsHasselblattRevised-1.pdf. I’ll have to look this over tonight…
Thanks for pointing me to cool ideas!
Consider this map on the unit interval: f(x) = 2x mod 1. It is chaotic, with a Lyapunov exponent of ln 2, unstable periodic orbits of all orders, etc. But when x is expressed in binary, it’s just the shift map, 0.x1 x2 x3… -> 0.x2 x3…, making it computationally trivial.
Examples like this have convinced me that chaos and computational complexity are not particularly related: chaos is mainly about the amount of information, i.e., the number of bits, that you need to predict the future t steps in advance (which here grows as t). Computation is what you do with this information, and some chaotic systems don’t do much with it.
Heuristically, systems that are computationally complex tend to be less chaotic. My Ph.D. thesis was about simulating Turing machines with maps and flows in two and three dimensions, where the digit sequence shifts left or right depending on the motion of the TM’s head. (This is all pretty trivial, but I didn’t know much about CS at the time, so it made a splash in the physics community in 1990.) A chaotic system then corresponds to a TM with an overall drift in its motion, moving Omega(t) steps away from its initial position after t steps. But a TM that is doing a complicated computation typically moves away from its initial position much more slowly than that, since it revisits the same places on its tape many times. In dynamical systems terms, if it moves o(t) steps away after t steps, then its Lyapunov exponent is zero — it is computationally complex, but not chaotic.
I missed your comment before i commented. But wow you did what? Thanks for that inspiring idea!
It is great that Wikipedia has articles for all natural numbers up through 217. Then it skips to 220 and 223 (a prime). Anyone want to fill the gap?
A fool’s errand: http://en.wikipedia.org/wiki/Interesting_number_paradox
I cannot follow you question. A simplistic example for a chaotic system is the tent map which formalizes simple kneading. The problem of predicting z_i is *exactly* the problem of getting z_0 with high precision.
If you flip the downward line of the tent to start at 0 and go up to 1 the map reduces exactly to the left bitshift operation (while cropping non fractional digits).
I cannot see what this would have to do with computational complexity. Someone ares to explain?
Maybe not relevant for the core of the blog, but almost all orbit types actually imply period 3… see “Almost all orbit types imply period-3” (Erik Lundberg). I think he identifies some cases in which such statement holds and then counts at least how many times that case happens among {1,…,n} orbits.
2^8=256, it is byte, so some basic types in Standard Pascal (and other programming languages) have size 256 ;))
Just a pedantic point: In giving the ordering of the intergers used in Sharkovsky’s theorem, you left out the powers of 2. They should appear at the end, in descending order (so that under this ordering the intergers are totally ordered with maximum element 2).
No, I forgot them…thanks
Hmmm … this posts asks in essence: Why is it tough to show that (classical) chaotic iterated maps are computationally hard?
Well … an engineering intuition is that these maps are not computationally hard … in essence because their “smoothed” quantum generalization is not hard:
Here the point is that (empirically at least) for a class of Lindbladian flows that is sufficiently general as to encompass all the quantum flows one meets in nature or in the laboratory, this theorem is not true: the intuition is that (generically noisy) Lindbladian flows generically compress quantum trajectories onto low-dimension submanifolds, such that the computational complexity computing trajectories as integral curves, to finite accuracy, is generically very much smaller than dim
.
Pulling this “Lindbladian compression” intuition back to the classical domain suggests that even if computing individual trajectories is computationally hard, the properties of trajectory ensembles may be computationally easy to estimate—which in practice is what one mainly wants to know.
In other words, perhaps this is a class of questions in which, from a trajectory-unravelling point-of-view, upper-bound complexity theorems, and even concrete algorithms, are more natural and useful than lower-bound theorems? It seems to me that a great deal of practical work (and possibly fundamental work too) might be accomplished along these lines.
Comment prologue: 256 th ? 2^8 ? Digital ! I could not resist…
Dissertation: Just to remind beginners that what you call BCT is just what is usually called Dynamical Systems (DS thereoff). As it is well known, dynamical systems can be studied as models of real systems, physical (that was the motivation of Poincaré; a discussion about complexity issues here: http://physics.stackexchange.com/questions/252/the-many-body-problem ), etc, etc and etc, or just as mathematical objects, of interest independently of their realization. An important divide in the world of dynamical systems is continous and discrete.
Regarding continous DS a good introduction is http://www.ams.jhu.edu/~ers/book.pdf, which covers some algorithmic issues but the related computational complexity ones. Those has been studied by Braverman (in fact some of its work could be titled “The complexity of complex complex systems”), and others.
Regarding complexity issues of discrete DS (more updated than Papadimitrou´ s), a good updated source is this PHD thesis, which however focus more on the counting complexity of discrete DSs: http://osl.cs.uiuc.edu/docs/PhD-thesis-TR/PhD-thesis-TR-nov.pdf.
According to C.Moore´s above comment chaos and computational hardness might be “orthogonal”. From the same author a short and nice summary of the relations of real physical dynamical systems and abstract dynamical systems bridged by computational complexity issues is this paper: http://arxiv.org/PS_cache/cond-mat/pdf/0109/0109010v1.pdf.
Comment epilogue: Formalizability, decidability, complexity and parallelizability, these are the questions !
Comment epilogue: Formalizability, decidability, complexity and parallelizability, these are the questions !
Perhaps a physics topic which is more closely linked to computational complexity than chaotic behavior is: renormalization group (RG) and phase transitions. I’d love to see a Lipton/Regan blog post on the connection between complexity theory and RG.
Second the motion for an RG post. It was Richard Hamming, in his AMS Monthly essay “The unreasonable effectiveness of mathematics” (1980), who was among the first to plainly assert a principle of orthodoxy that most undergraduate QM texts respect:
On the other, in recent decades a great deal of progress has come via computational methods (DDMRG for example) that flout Hamming’s principle pretty vigorously … and so it is good for mathematicians, scientists, and engineers to have at least some idea of the circumstances under which Hamming’s QM orthodoxy can profitably be abandoned, and the practical uses of the computational methods that result.