Άρθρο: Butterflies And Complexity Theories

Βρήκες ή ψάχνεις κάτι ενδιαφέρον για τους τομείς των Μαθηματικών, της Φυσικής ή της Πληροφορικής; Για πέρνα να τα πούμε...

Συντονιστές: kostas213, markelos, Tulis

Απάντηση
Άβαταρ μέλους
antony07
Forum Moderator
Forum Moderator
Δημοσιεύσεις: 1673
Εγγραφή: Τετ Νοέμ 15, 2006 4:37 pm
Real Name: Αντώνης
Gender: Male
Facebook ID: 0
Τοποθεσία: Uncertain (by principle)
Επικοινωνία:

Άρθρο: Butterflies And Complexity Theories

Δημοσίευση από antony07 »

(Είπα να ξεκινήσω να συνεισφέρω στην επιστημονική γωνίτσα του φόρουμ με αυτό. Ίσως σας φανεί λίγο εξειδικευμένο, αλλά δεν χάνετε τίποτα να το κοιτάξετε (έστω και διαγώνια). Όποιος έχει κάτι με το οποίο ασχολείται (διπλωματική κλπ), ή κάποιος που έχει διαβάσει κάτι που του φάνηκε ενδιαφέρον ας το μοιραστεί με όλους μας :wink: )

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 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 P or is PSPACE-complete according to whether the property is invariant under permutations of the (names of the) states. Thus again, the complexity of complexity is open.

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
"Ωραία παιδιά κατάχαμα κυλάει
το πιο ωραίο ρόδο απ' το στεφάνι σας
αδράξτε κάθε τι που προσπερνάει
μα αν σε βιτρίνα εμπρός βρεθεί η χάρη σας
ή σε γκισέ, φυλάξτε το τομάρι σας
θυμάστε, Colin de Cayeux τον λέγανε
το άσυλο εμπιστεύτηκε ναι σαν κι εσάς,
σημάδεψε ο μπάτσος και τον ξέκανε
"
palasso
Δημοσιεύσεις: 431
Εγγραφή: Κυρ Ιούλ 04, 2010 3:55 pm
Real Name: Vassilis
Gender: Male
Facebook ID: 0

Re: Άρθρο: Butterflies And Complexity Theories

Δημοσίευση από palasso »

Πάντα για κάποιο λόγο είχα μία παρόμοια απορία-αναζήτηση... Την σύνδεση των μαθηματικών (συγκεκριμένα μαθηματική λογική) με την πληροφορική (συγκεκριμένα computational complexity (αλλά και decidability)).

Κατέληξα πλέον (τον Ιούλιο) να εντοπίσω την Descriptive Complexity Theory η οποία συνδέει τις κλάσεις πολυπλοκότητας με μαθηματικές λογικές. Συγκεκριμένα στόχος της θεωρίας είναι να αναζητήσει πόση λογική εκφραστικότητα απαιτείται μία γλώσσα να έχει προκειμένου να περιγράψει κάποια ιδιότητα (Το ανάλογο του "πόσο δύσκολο είναι να ελέγξουμε αν η είσοδος σε έναν αλγόριθμο έχει κάποια ιδιότητα"). Η θεωρία είναι υποκλάδος των Computational Complexity Theory και Finite Model Theory. Μπορεί κανείς να διαβάσει τα αποτελέσματα που προέκυψαν (αλλά και πως αποδεικνύονται και να πάρει μία ιδέα) στο βιβλίο του Neil Immerman, Descriptive Complexity.

Μία σύντομη γραφική αναπαράσταση των αποτελεσμάτων:
[imgr 700x1200]http://www.cs.umass.edu/~immerman/descriptiveWorld.jpg[/imgr]

Η Descriptive Complexity Theory χρησιμοποιείται πολλές φορές για τον σχεδιασμό κυκλωμάτων. Επίσης τον Αύγουστο είχε προκύψει μία προσπάθεια επίλυσης του P vs NP η οποία χρησιμοποιούσε εκτενώς αυτήν την θεωρία (μία από τις επικροτήσεις για τεχνικές που εισήγαγε(ή "εκλαΐκευσε) η (αποτυχημένη τελικά [1], [2]) απόδειξη).

Εκτός από την Descriptive Complexity Theory, έχει γίνει μία σύνδεση των 2 κλάδων και σε άλλες θεωρίες (π.χ. Proof Complexity) που χρησιμεύουν στους theorem provers και semantic reasoners (π.χ. Analytic Tableau, Resolution)


Όσον αφορά την σύνδεση μεταξύ Computational Complexity Theory και Complex Systems, τις τελευταίες δεκαετίες έχουν γίνει κάποιες προσπάθειες.

Μία διαισθητική και γραφική προσέγγιση αποτελεί η προσπάθεια που έγινε από τον Stephen Wolfram που αναλύει το "programme" του στο βιβλίο του a New Kind of Science. Συγκεκριμένα αναπτύσσει παραδείγματα κυτταρικών αυτομάτων στα οποία παρατηρεί κάποιες ιδιότητες που αφορούν την απλότητα περιγραφής των αλγορίθμων που τα "τρέχουν", την ταχύτητα με την οποία τρέχουν καθώς επίσης και τους γραφικούς σχηματισμούς τους οποίους κάνουν (που παραπέμπουν σε fractals).

Ένα κυτταρικό αυτόματο:
Εικόνα

Μέσα από το βιβλίο του καταλήγει σε κάποια συμπεράσματα και αρχές όπως Computational irreducibility, Principle of computational equivalence (οι οποίες αν και έχουν ενδιαφέρουσα διατύπωση, στην πραγματικά πρόκειται για επαναδιατυπώσεις παλαιότερων θεμελιωδών θεωρημάτων (π.χ. Θεωρήματα μη-πληρότητας Godel) και θέσεων (π.χ. Church-Turing thesis) τις οποίες δεν αναφέρει και δέχτηκε έντονη κριτική για λογοκλοπή)
Μία αρκετά ενδιαφέρουσα "διαισθητική" ταξινόμηση που κάνει στο βιβλίο του είναι οι Wolfram classes. Πρόκειται για 4 κλάσεις οι οποίες περιγράφουν την δυσκολία προβλεψιμότητας των σχημάτων που παράγονται σε ένα κυτταρικό αυτόματο. Συγκεκριμένα κάποια κυτταρικά αυτόματα όπως το Rule 110 αποδείχτηκαν ότι είναι Turing-complete[Cook] και ο Wolfram τα χαρακτηρίζει ως Class 4 στην τάξη του.

Rule 110:
Εικόνα
Παρατηρήστε τα διαστημόπλοια (τρίγωνα) και τις κανονικότητες που παράγονται

Κάποιες περισσότερο "μαθηματικές" προσεγγίσεις μπορεί να προκύψουν τα επόμενα χρόνια από την σύνδεση των Complex Systems με θεωρίες από Arithmetical hierarchy, Systems theory, Real closed fields κ.α. (προσωπική εκτίμηση)
Απάντηση

Επιστροφή στο “Ζητήματα Μαθηματικών - Φυσικής - Πληροφορικής”