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