Complexity

In General > s.a. chaos; computation [complexity classes] and quantum computing; critical phenomena.
* Complex system: An aggregate of individual "agents" each of which acts independently, but can react as a whole to changes in the systems environment.
* Goal: Complexity theory studies questions like, How do simple laws give rise to intricate structure? (Sensitive dependence on initial conditions); Why are intricate structures so ubiquitous? Why do they often embody their own kind of simple law?
* Features: Many complex phenomena have a power law behavior, such that the probability for an even goes like some power of the event's "size," arising from interactions of components at many scales; Complexity is related to information, but is not adequately quantified by information needed to describe something, or shortest algorithm size; Logical depth (Bennett) is impractical; breadth (Lloyd & Pagels) seems better.
* Approaches: Self-organized criticality (SOC); Highly optimized tolerance (HOT).
* Remark: Have to distinguish complexity from randomness, they are not the same!

Applications and Examples > s.a. classical systems; cosmology; fractal; partial differential equations; posets; quantum gravity.
* Idea: It is giving insight into the effectiveness of math in describing nature, and stimulating a shift in paradigms in physics, stimulated by computer simulations now possible (e.g., cellular automata); Proposed as foundation for the formulation of various concepts in physics, such as the Lagrangian formulation of particle mechanics (Soklakov).
* Types of phenomena:
- Simple phenomena; Linear of chaotic with few degrees of freedom, or possibly equilibrium states of many degrees of freedom.
- Complex phenomena; Characterized by contingency and variability.
- Critical phenomena; (a) Boundaries between phases in therm (fragile, need fine tuning); (b) Self-organized systems (robust, exhibit punctuated equil, small changes also lead to large variations).
* Applications: Hydrodynamic flow, astrophysics, solid state, lasers; marketing, investment, industrial design.
@ And cosmology: comments to Vilenkin PRD(88); Rosu NCB(95)ap/94 [sub-horizon scales]; Cirkovic FP(02)qp/01; Sylos Labini & Gabrielli PhyA(04)ap-in [structures].
@ Algorithmic complexity: Zurek Nat(89)sep [and thermodynamic cost of computations]; Batterman & White FP(96).
@ Other examples: Parisi cm/94 [biology]; Drossel PRL(99) [hierarchical structures]; Boffetta et al PRP(02) [and predictability]; Sant'Anna mp/04 [and entropy]; Meyer-Ortmanns PhyA(04)cm/03 [networks]; Prosen a0704-JPA [chains of quantum particles].

References > s.a. Emergence, Scaling.
@ I, books: Bonner 88; Levy 92; Lewin 92; Waldrop 92; Gell-Mann 94; Coveney & Highfield 95; Holland 95.
@ I, articles: Zabusky PT(87)oct; Lloyd ThSc(90); Maddox Nat(90)apr [no single measure], Nat(90)oct [order within chaos]; Horgan SA(95)jun.
@ II, books: Nicolis & Prigogine 89; Mainzer 97.
@ General: Bennett FP(86); Grassberger IJTP(86); Lloyd & Pagels AP(88); Lloyd Compl(99).
@ Quantum: Cleve qp/99-in [review]; Mora et al qp/06 [quantum Kolmogorov complexity].
@ Self-organized criticality: Bak & Paczuski PW(93)dec.
@ Highly optimized tolerance: Carlson & Doyle PRE(99), PRL(00); Doyle & Carlson PRL(00).
@ Measures of complexity: Feldman & Crutchfield PLA(98), Martin et al PLA(03) [statistical]; Stoop et al JSP(04) [obstruction to predictability]; Martin et al PhyA(06) [bounds].
@ Techniques: Marwan et al PRP(07) [recurrence plots].
@ And information: Parlett BAMS(92); Traub & Werschulz 98; Gell-Mann Lloyd Compl(96) [information measures]; McAllister PhSc(03) [Gell-Mann's effective complexity]; > s.a. Brudno's Theorem, quantum information.
@ And physics: Ford in(93); Batterman & White FP(96); Kirilyuk AFLdB(96)qp/98 [quantum mechanics]; Kreinovich & Longpre IJTP(98) [relevance]; Yurtsever qp/02 [simple rules?]; Segre IJTP(04) [classical and quantum objects]; Allegrini et al CSF(04) [and randomness]; Nicolis CSF(05) [mechanisms for reducing complexity].

Main page – Abbreviations – Journals – Comments – Other sites – Acknowledgements
Send feedback and suggestions to bombelli at olemiss.edu – Modified 21 jun 2008