Complexity| Complexity |
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: We 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-conf [uncountably many classical and quantum complexity classes];
Gómez a1911 [quantum algorithms and time];
> 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; Complexity = Action
Proposal; fractal; partial derivatives.
* 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 how hard it is 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);
Balasubramanian et al a1905
[quantum time evolution with chaotic Hamiltonians].
@ 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];
Brandão et al a2003 [growth models];
> s.a. many-body systems [information scrambling].
@ Laws of complexity: Brown & Susskind PRD(18)-a1701 [thermodynamics of quantum complexity, second law];
Bernamonti et al PRL(19)-a1903 [first law, variation of holographic complexity];
Shah & Gorard a1910 [laws, and quantum cellular automata];
Bernamonti et al a2002 [first law].
@ Continuous systems, field theory:
Chapman et al PRL(18)-a1707 [quantum-many body systems];
Yang et al EPJC(19)-a1803;
Huang a1905 [operator approach];
> s.a. causality in quantum theory.
@ 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(16)-a1611 [information content of cosmic structures];
> s.a. big bang; entropic gravity.
@ 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];
Janik & Witaszczyk a2006 [deep neural networks].
@ 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];
Carmi et al JHEP(17)-a1612 [holographic complexity];
Shangnan a1902 [and entropy, Markov chains];
> 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);
issue CSF(04);
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];
Fontanelli et al a2002 [rev, and probabilistic concepts].
@ 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];
Ali et al JHEP(19)-a1810 [time evolution].
@ Techniques: Marwan et al PRP(07) [recurrence plots];
Friedrich et al PRP(11) [stochastic methods];
Felice et al Chaos(18)-a1804 [information geometry].
@ 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 page
– abbreviations
– journals – comments
– other sites – acknowledgements
send feedback and suggestions to bombelli at olemiss.edu – modified 25 apr 2021