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__: 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 page – abbreviations – journals – comments – other
sites – acknowledgements

send feedback and suggestions to bombelli at olemiss.edu – modified
28 jul 2017