hn-classics/_stories/2001/14119465.md

---
created_at: '2017-04-15T04:57:43.000Z'
title: 'Measures of Complexity: A non-exhaustive list (2001) [pdf]'
url: http://web.mit.edu/esd.83/www/notebook/Complexity.PDF
author: breck
points: 92
story_text: 
comment_text: 
num_comments: 7
story_id: 
story_title: 
story_url: 
parent_id: 
created_at_i: 1492232263
_tags:
- story
- author_breck
- story_14119465
objectID: '14119465'
year: 2001

---
[Source](http://web.mit.edu/esd.83/www/notebook/Complexity.PDF "Permalink to ")

%PDF-1.2 % 10 0 obj << /Length 11 0 R >> stream BT 222.75 705.75 TD 0 0 0 rg /F0 15.75 Tf 0.164 Tc 0.0235 Tw (Measures of Complexity) Tj 11.25 -24 TD 0.0872 Tc -0.2747 Tw (a non--exhaustive list) Tj 42 -21.75 TD /F0 12.75 Tf 0.0308 Tc 0.5317 Tw (Seth Lloyd) Tj -123 -20.25 TD /F1 12 Tf -0.042 Tc 0.417 Tw (d'Arbeloff Laboratory for Information Systems and Technology) Tj 58.5 -20.25 TD -0.0162 Tc 0.0162 Tw (Department of Mechanical Engineering) Tj 2.25 -19.5 TD -0.0362 Tc 0.5362 Tw (Massachusetts Institute of Technology) Tj 54 -20.25 TD 0.0373 Tc 0 Tw (slloyd@mit.edu) Tj -177.75 -19.5 TD -0.0884 Tc 0.4634 Tw ( The world has grown more complex recently, and the number of ways of measuring) Tj 0 -13.5 TD -0.066 Tc 0.4698 Tw (complexity has grown even faster. This multiplication of measures has been taken by) Tj 0 -14.25 TD -0.0559 Tc 0.3372 Tw (some to indicate confusion in the field of complex systems. In fact, the many measures) Tj 0 -13.5 TD -0.0551 Tc 0.4013 Tw (of complexity represent variations on a few underlying themes. Here is an (incomplete)) Tj 0 -14.25 TD -0.0688 Tc 0.4855 Tw (list of measures of complexity grouped into the corresponding themes.) Tj 0 -19.5 TD -0.0461 Tc 0.2768 Tw (An historical analog to the problem of measuring complexity is the problem of describing) Tj 0 -13.5 TD -0.0157 Tc 0.0907 Tw (electromagnetism before Maxwell's equations. In the case of electromagnetism,) Tj 0 -14.25 TD -0.0272 Tc 0.2147 Tw (quantities such as electric and magnetic forces that arose in different experimental) Tj 0 -13.5 TD -0.0364 Tc 0.241 Tw (contexts were originally regarded as fundamentally different. Eventually it became) Tj 0 -14.25 TD -0.0808 Tc 0.4557 Tw (clear that electricity and magnetism were in fact closely related aspects of the same) Tj 0 -13.5 TD -0.0317 Tc 0.2567 Tw (fundamental quantity, the electromagnetic field. Similarly, contemporary researchers in) Tj T* -0.0437 Tc 0.377 Tw (architecture, biology, computer science, dynamical systems, engineering, finance, game) Tj 0 -14.25 TD -0.0759 Tc 0.3973 Tw (theory, etc., have defined different measures of complexity for each field. Because) Tj 0 -13.5 TD -0.0338 Tc 0.2213 Tw (these researchers were asking the same questions about the complexity of their different) Tj 0 -14.25 TD -0.0973 Tc 0.4973 Tw (subjects of research, however, the answers that they came up with for how to measure) Tj 0 -13.5 TD -0.0249 Tc 0.0249 Tw (complexity bear a considerable similarity to ) Tj 213 0 TD -0.0366 Tc 0.3366 Tw (eachother. Three questions that researchers) Tj -213 -13.5 TD -0.0651 Tc 0.3378 Tw (frequently ask to quantify the complexity of the thing (house, bacterium, problem,) Tj 0 -14.25 TD -0.0624 Tc 0.3124 Tw (process, investment scheme) under study are) Tj 0 -19.5 TD -0.1553 Tc 0.6553 Tw (1. How hard is it to describe?) Tj 0 -20.25 TD -0.1653 Tc 0.6653 Tw (2. How hard is it to create?) Tj 0 -19.5 TD -0.0587 Tc 0.3087 Tw (3. What is its degree of organization?) Tj T* -0.0679 Tc 0.4679 Tw (Here is a list of some measures of complexity grouped according to the question that they) Tj 0 -14.25 TD -0.0304 Tc 0.1668 Tw (try to answer. Measures within a group are typically closely related quantities.) Tj 0 -39.75 TD /F0 12 Tf 0.1003 Tc -0.3503 Tw (1. Difficulty of description) Tj 135 0 TD /F1 12 Tf -0.1262 Tc 0.4262 Tw (. Typically measured in bits.) Tj -135 -19.5 TD -0.055 Tc 0 Tw (Information;) Tj 0 -19.5 TD -0.1875 Tc (Entropy;) Tj 0 -20.25 TD -0.041 Tc 0.341 Tw (Algorithmic Complexity or Algorithmic Information Content;) Tj 0 -19.5 TD -0.0734 Tc 0.8234 Tw (Minimum Description Length;) Tj 0 -20.25 TD -0.0367 Tc 0.0367 Tw (Fisher Information;) Tj ET endstream endobj 11 0 obj 3758 endobj 4 0 obj << /Type /Page /Parent 5 0 R /Resources << /Font << /F0 6 0 R /F1 8 0 R >> /ProcSet 2 0 R >> /Contents 10 0 R >> endobj 13 0 obj << /Length 14 0 R >> stream BT 90 709.5 TD 0 0 0 rg /F1 12 Tf -0.186 Tc 0.936 Tw (Renyi Entropy;) Tj 0 -20.25 TD -0.0369 Tc 0.0369 Tw (Code Length (prefix-free, Huffman, Shannon-) Tj 222 0 TD -0.0255 Tc 0.4005 Tw (Fano, error-correcting, Hamming);) Tj -22
Tufte CSS, upgrade jekyll, add metadata, index 2018-02-23 18:58:03 +00:00			`---`
			`created_at: '2017-04-15T04:57:43.000Z'`
			`title: 'Measures of Complexity: A non-exhaustive list (2001) [pdf]'`
			`url: http://web.mit.edu/esd.83/www/notebook/Complexity.PDF`
			`author: breck`
			`points: 92`
			`story_text:`
			`comment_text:`
			`num_comments: 7`
			`story_id:`
			`story_title:`
			`story_url:`
			`parent_id:`
			`created_at_i: 1492232263`
			`_tags:`
			`- story`
			`- author_breck`
			`- story_14119465`
			`objectID: '14119465'`
Adds year as metadata to all stories 2018-06-08 12:05:27 +00:00			`year: 2001`
Tufte CSS, upgrade jekyll, add metadata, index 2018-02-23 18:58:03 +00:00
			`---`
Initial commit 2018-02-23 18:19:40 +00:00			`[Source](http://web.mit.edu/esd.83/www/notebook/Complexity.PDF "Permalink to ")`

			%PDF-1.2 % 10 0 obj << /Length 11 0 R >> stream BT 222.75 705.75 TD 0 0 0 rg /F0 15.75 Tf 0.164 Tc 0.0235 Tw (Measures of Complexity) Tj 11.25 -24 TD 0.0872 Tc -0.2747 Tw (a non--exhaustive list) Tj 42 -21.75 TD /F0 12.75 Tf 0.0308 Tc 0.5317 Tw (Seth Lloyd) Tj -123 -20.25 TD /F1 12 Tf -0.042 Tc 0.417 Tw (d'Arbeloff Laboratory for Information Systems and Technology) Tj 58.5 -20.25 TD -0.0162 Tc 0.0162 Tw (Department of Mechanical Engineering) Tj 2.25 -19.5 TD -0.0362 Tc 0.5362 Tw (Massachusetts Institute of Technology) Tj 54 -20.25 TD 0.0373 Tc 0 Tw (slloyd@mit.edu) Tj -177.75 -19.5 TD -0.0884 Tc 0.4634 Tw ( The world has grown more complex recently, and the number of ways of measuring) Tj 0 -13.5 TD -0.066 Tc 0.4698 Tw (complexity has grown even faster. This multiplication of measures has been taken by) Tj 0 -14.25 TD -0.0559 Tc 0.3372 Tw (some to indicate confusion in the field of complex systems. In fact, the many measures) Tj 0 -13.5 TD -0.0551 Tc 0.4013 Tw (of complexity represent variations on a few underlying themes. Here is an (incomplete)) Tj 0 -14.25 TD -0.0688 Tc 0.4855 Tw (list of measures of complexity grouped into the corresponding themes.) Tj 0 -19.5 TD -0.0461 Tc 0.2768 Tw (An historical analog to the problem of measuring complexity is the problem of describing) Tj 0 -13.5 TD -0.0157 Tc 0.0907 Tw (electromagnetism before Maxwell's equations. In the case of electromagnetism,) Tj 0 -14.25 TD -0.0272 Tc 0.2147 Tw (quantities such as electric and magnetic forces that arose in different experimental) Tj 0 -13.5 TD -0.0364 Tc 0.241 Tw (contexts were originally regarded as fundamentally different. Eventually it became) Tj 0 -14.25 TD -0.0808 Tc 0.4557 Tw (clear that electricity and magnetism were in fact closely related aspects of the same) Tj 0 -13.5 TD -0.0317 Tc 0.2567 Tw (fundamental quantity, the electromagnetic field. Similarly, contemporary researchers in) Tj T* -0.0437 Tc 0.377 Tw (architecture, biology, computer science, dynamical systems, engineering, finance, game) Tj 0 -14.25 TD -0.0759 Tc 0.3973 Tw (theory, etc., have defined different measures of complexity for each field. Because) Tj 0 -13.5 TD -0.0338 Tc 0.2213 Tw (these researchers were asking the same questions about the complexity of their different) Tj 0 -14.25 TD -0.0973 Tc 0.4973 Tw (subjects of research, however, the answers that they came up with for how to measure) Tj 0 -13.5 TD -0.0249 Tc 0.0249 Tw (complexity bear a considerable similarity to ) Tj 213 0 TD -0.0366 Tc 0.3366 Tw (eachother. Three questions that researchers) Tj -213 -13.5 TD -0.0651 Tc 0.3378 Tw (frequently ask to quantify the complexity of the thing (house, bacterium, problem,) Tj 0 -14.25 TD -0.0624 Tc 0.3124 Tw (process, investment scheme) under study are) Tj 0 -19.5 TD -0.1553 Tc 0.6553 Tw (1. How hard is it to describe?) Tj 0 -20.25 TD -0.1653 Tc 0.6653 Tw (2. How hard is it to create?) Tj 0 -19.5 TD -0.0587 Tc 0.3087 Tw (3. What is its degree of organization?) Tj T* -0.0679 Tc 0.4679 Tw (Here is a list of some measures of complexity grouped according to the question that they) Tj 0 -14.25 TD -0.0304 Tc 0.1668 Tw (try to answer. Measures within a group are typically closely related quantities.) Tj 0 -39.75 TD /F0 12 Tf 0.1003 Tc -0.3503 Tw (1. Difficulty of description) Tj 135 0 TD /F1 12 Tf -0.1262 Tc 0.4262 Tw (. Typically measured in bits.) Tj -135 -19.5 TD -0.055 Tc 0 Tw (Information;) Tj 0 -19.5 TD -0.1875 Tc (Entropy;) Tj 0 -20.25 TD -0.041 Tc 0.341 Tw (Algorithmic Complexity or Algorithmic Information Content;) Tj 0 -19.5 TD -0.0734 Tc 0.8234 Tw (Minimum Description Length;) Tj 0 -20.25 TD -0.0367 Tc 0.0367 Tw (Fisher Information;) Tj ET endstream endobj 11 0 obj 3758 endobj 4 0 obj << /Type /Page /Parent 5 0 R /Resources << /Font << /F0 6 0 R /F1 8 0 R >> /ProcSet 2 0 R >> /Contents 10 0 R >> endobj 13 0 obj << /Length 14 0 R >> stream BT 90 709.5 TD 0 0 0 rg /F1 12 Tf -0.186 Tc 0.936 Tw (Renyi Entropy;) Tj 0 -20.25 TD -0.0369 Tc 0.0369 Tw (Code Length (prefix-free, Huffman, Shannon-) Tj 222 0 TD -0.0255 Tc 0.4005 Tw (Fano, error-correcting, Hamming);) Tj -22