Complexity definitions

1. Computational Complexity = speed/memory scaling P, NP

2. Algorithmic Randomness (Chaitin-Kolmogorov)

3. Entropy/information

4. Physical complexity

(Bernoulli-Turing Machine)

Crutchfield & Young in Complexity, Entropy, & the Physics of Information 1990 pp.223-269

www.santafe.edu/~jpc/JPCPapers.html

Sole & Goodwin, Signs of Life 2000

Previous slide

Next slide

Back to first slide

View graphic version