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 [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; 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];
Brown & Susskind PRD(18)-a1701 [thermodynamics of quantum complexity, second law];
> s.a. many-body systems [information scrambling].

@ __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. 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].

@ __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].

@ __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 26 may 2019