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!

Computational Complexity > s.a. computation.
* In general: The study of how the computation time scales with the size of the input; There are different classes, including BQP and NP.
* NP problems: There is no known algorithm that will solve them in polynomial time; Non-deterministic methods (evolutionary search and quantum computers) have been proposed.
@ Algorithmic complexity: Zurek Nat(89)sep [and thermodynamic cost of computations]; Batterman & White FP(96).
@ NP completeness: Garey & Johnson 79; Greenwood qp/00-in [methods]; Nussinov & Nussinov cm/02 [approach to graph problems]; Mao PRA(05)qp/04 [polynomial time in quantum computers]; Aaronson qp/05 [and physical reality]; Zak & Fijany PLA(05) [using quantum resonances]; Rojas qp/06 [interpolating problem with BQP]; > s.a. statistical mechanics.
@ Examples: Gottesman & Irani a0905 [NEXP-complete classical tiling problem and QMA_EXP-complete quantum Hamiltonian problem].

Other Applications and Examples > s.a. classical systems; cosmology; fractal; partial differential equations; posets; quantum gravity.
* Dynamical systems: In classical mechanics complexity is characterized by the rate of local exponential instability, which effaces the memory of
initial conditions and leads to practical irreversibility; Quantum mechanics instead appears to exhibit strong memory of the initial state, and the notion of complexity of a system needs to be based on other notions, such as its stability and reversibility properties.
* Remark: 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 thermodynamics (fragile, need fine tuning); (b) Self-organized systems (robust, exhibit punctuated equilibrium, small changes also lead to large variations).
* Applications: In physics, hydrodynamic flow, astrophysics, solid state, lasers; In other fields, marketing, investment, industrial design.
@ And physics: Ford in(93); Batterman & White FP(96); Kirilyuk AFLB(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]; Benenti & Casati PRE(09)-a0808 [quantum system].
@ 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].
@ Hierarchical structures: Drossel PRL(99); Olemskoi et al PhyA(09).
@ Other examples: Parisi cm/94 [biology]; Boffetta et al PRP(02) [and predictability]; Sant'Anna mp/04 [and entropy]; Meyer-Ortmanns PhyA(04)cm/03 [networks]; Prosen JPA-a0704 [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)sep; 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]; López-Ruiz et al a0905 [complexity measures].
@ 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)apr [Gell-Mann's effective complexity]; > s.a. Brudno's Theorem, quantum information.

main page – abbreviations – journals – comments – other sites – acknowledgements
send feedback and suggestions to bombelli at olemiss.edu – modified 21 may 2009