Forget about runtimes longer than simple exponential ===========Warren D Smith=====Aug 2015============== I saw that computer scientist Bernard Chazelle is now interested in "natural algorithms" which have been "refined by evolution for millions of years," and as a case in point, he in the rather awe-inspiring 106-page paper http://arxiv.org/abs/0905.4241 The Convergence of Bird Flocking (2009) examined the behavior of the "Cucker-Smale model of bird flocking," finding that an N-bird flock would take TIME upper bounded by 2^(2^(2^(...2))) steps to reach its final combinatorial configuration, where the number of 2's in the tower is <=4*lg(N), but, he showed, could under some circumstances exceed lg(N/2). The MODEL is: each bird is a moving point in 3-space, with piecewise-constant velocity vector. Each discrete time step (e.g. each second) the bird readjusts its velocity vector to be a convex combination of its old velocity and the average velocity of itself and that of its "neighbors," i.e. of all other birds within distance 1. He allows the coefficients in the combination (which he calls the "self confidence" factor for that bird) to vary with the bird and with time, in some way he still has not explained after 20 pages (I think he is allowing any such rule and considering the one that yields slowest convergence? His theorem statements and claims in "The Results" section unfortunately ignore this issue), and also you stay my "neighbor" even if your distance from me gets slightly greater than 1 (which Chazelle calls "hysteresis"). What do I have to say about this? I have to say that this model is biophysically wrong. It is not how birds flock. And more importantly, NO ALGORITHM RUNNING IN OUR UNIVERSE CAN TAKE LONGER THAN SIMPLE EXPONENTIAL TIME exp(polynomial(N)) WHERE N IS THE NUMBER OF PARTICLES INVOLVED. Which means that everything Chazelle or anyone else considers that takes, say, double-exponential time, is physically irrelevant. Because of two effects. In the below, let E be the minimum escape energy for any of the N particles (or subsets thereof) in the physical system (E may vary with time). Effect #1: tunneling into a black hole. Consider N particles. For example, the planet Earth consists of about N=1.5*10^52 elementary particles (quarks and electrons). There is a nonzero chance they will quantum-tunnel though the high potential-energy-of-compression barrier to form a black hole. In fact, I claim the expected lifetime of the Earth (or whatever system) before this happens, is upper bounded by exp(C*N^P/E^Q) for some absolute positive constant C and where P and Q also are constants with 0<P<4, 0<Q<4. Effect #2: evaporation. Consider N particles at finite positive temperature T. There at any time is a positive chance one (or a bound subset) of the particles will, just due to thermal fluctuations, attain escape velocity and leave, never to be seen again. This characteristic escape time seems upper bounded by K * N^R * exp(-E/T) where E is the escape energy reckoned as a temperature and K,R are some constants. Note in our universe T is lower bounded by the positive constant "Gibbons Hawking temperature." Combining these 2 effects, we see that no matter what E is, the system will self-destruct in expected simple exponential time at most. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)