In General > s.a. chaos; critical phenomena.
* Complex system: An aggregate of individual "agents" each of which acts independently, which displays collective behavior that does not follow trivially from the behaviors of the individual parts, for example reacting as a whole to changes in the system's environment; Examples include condensed-matter systems, ecosystems, stock markets and economies, biological evolution, and the whole of human society; Progress has been made in the quantitative understanding of complex systems since the 1980s, using a combination of basic theory and computer simulation.
* 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 the 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 Classes > s.a. computation and quantum computing.
* In general: The study of how the computation time scales with the size of the input; There are many 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; > s.a. mathematics [Millennium Problems].
@ General references: Rodríguez-Laguna & Santalla JSM(14)-a1010 [physical consequences of P ≠ NP]; Manin JPCS(14)-a1302 [and physics].
@ Algorithmic complexity: Zurek Nat(89)sep [and thermodynamic cost of computations]; Batterman & White FP(96); Dimitrijevs & Yakaryılmaz a1608 [uncountably many classical and quantum complexity classes]; > s.a. quantum cosmology; realism.
@ NP completeness: Garey & Johnson 79; Greenwood qp/00-conf [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; fractal; partial .
* 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: Complexity 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); It has been proposed as foundation for the formulation of various concepts in physics, such as the Lagrangian formulation of particle mechanics (Soklakov).
* Hamiltonian complexity: A discipline that studies the question, How hard is it to simulate a physical system?
* Types of phenomena:
- Simple phenomena; Chaotic systems 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.
@ Physics: Ford in(93); Batterman & White FP(96); Kreinovich & Longpre IJTP(98) [relevance]; Yurtsever qp/02 [simple rules?]; Allegrini et al CSF(04) [and randomness]; Nicolis CSF(05) [mechanisms for reducing complexity]; Kwapień & Drożdż PRP(11).
@ Quantum physics: Kirilyuk AFLB(96)qp/98; Cleve qp/99-in [review]; Segre IJTP(04) [classical and quantum objects]; Mora et al qp/06 [quantum Kolmogorov complexity]; Benenti & Casati PRE(09)-a0808; Balachandran et al PRE(10)-a1009 [many-body dynamics, phase-space approach]; Anders & Wiesner Chaos(11)-a1110 [and quantum correlations]; Brown & Susskind a1701 [thermodynamics of quantum complexity]; Chapman et al a1707 [continuous quantum-many body systems].
@ Cosmology: comments to Vilenkin PRD(88); Rosu NCB(95)ap/94 [sub-horizon scales]; Ćirković FP(02)qp/01; Sylos Labini & Gabrielli PhyA(04)ap-in [structures]; Vazza MNRAS-a1611 [information content of cosmic structures].
@ Hierarchical structures: Drossel PRL(99); Olemskoi et al PhyA(09).
@ Networks: Meyer-Ortmanns PhyA(04)cm/03; Felice et al JMP(14); Franzosi et al PRE(16)-a1410 [entropic measure].
@ Other examples: Parisi cm/94 [biology]; Boffetta et al PRP(02) [and predictability]; Sant'Anna mp/04 [and entropy]; Prosen JPA(07)-a0704 [chains of quantum particles]; > s.a. black holes; causality; posets; quantum gravity; spin models [spin glasses].

References > s.a. emergence; Scaling.
@ I, books: Bonner 88; Levy 92 [artificial life]; Lewin 92; Waldrop 92; Gell-Mann 94; Coveney & Highfield 95; Holland 95; Auyang 98.
@ 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; Chaisson SWJ(14)-a1406 [global history for a wide spectrum of systems].
@ II, books: Nicolis & Prigogine 89; Mainzer 97; Mitchell 09 [r PT(10)feb].
@ General: Bennett FP(86); Grassberger IJTP(86); Lloyd & Pagels AP(88); Lloyd Compl(99); Osborne RPP(12)-a1106 [Hamiltonian complexity, rev]; Newman AJP(11)aug; Martín-Delgado ARBOR(13)-a1110-in [Turing's contribution]; Manin a1301-talk [Kolmogorov complexity in scientific discourse].
@ 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]; López-Ruiz et al JMP(09)-a0905 [quantum]; Cafaro et al AMC(10)-a1011 [information geometric construction of entropic indicators]; Manzano PhyA(12)-a1105 [Fisher-Shannon statistical measure, continuous variables]; Campbell & Castilho Piqueira a1110 [for quantum states]; Tan et al EPJP(14)-a1404 [new quantum measure of complexity]; Aaronson et al a1405 [and mixing of two liquids, rise and fall of complexity].
@ Techniques: Marwan et al PRP(07) [recurrence plots]; Friedrich et al PRP(11) [stochastic methods].
@ And information: Parlett BAMS(92); Traub & Werschulz 99; Gell-Mann Lloyd Compl(96) [information measures]; McAllister PhSc(03)apr [Gell-Mann's effective complexity]; > s.a. Brudno's Theorem; quantum information.
@ Related topics: Maldonado a1611 [and quantum theory, and time].

main pageabbreviationsjournalscommentsother sitesacknowledgements
send feedback and suggestions to bombelli at – modified 28 jul 2017