4 ms·

Measures of Complexity: A non-exhaustive list (2001) [pdf]

92 points by breck 10y ago

elevates 10y ago
From the same author this MOOC (Introduction to Information Theory): https://www.complexityexplorer.org/tutorials/55-introduction-to-information-theory https://www.complexityexplorer.org/tutorials/55-introduction... Recommended for (Introduction to Renormalization): https://www.complexityexplorer.org/tutorials/67-introduction-to-renormalization https://www.complexityexplorer.org/tutorials/67-introduction...
- stangls 10y ago
  Measuring computational complexity with dollars is a time dependent expression of complexity, since that value will change in the future due to cheaper and better hardware. An expression line number of operations or expression via Landau symbols is timeless and can be individually mapped to costs.
mafribe 10y ago
That list is pretty ad-hoc, and doesn't seem to be carefully curated. Fair enough, one has to start somewhere, but ... There is clearly a great deal of overlap, e.g. Minimum Description Length, algorithmic complexity and information theoretic entropy. There are also many well-understood relationships between different forms of complexity, e.g. between space and time complexity. Some appear to be less formal than others, e.g. what is "cost" what is "crypticity"? Finally, regarding the broad distinctions, in what sense are the "difficulty of description" and the "degree of organization" even different?
- moxious 10y ago
  I think he just didn't define complexity at all, just gave ways of measuring whatever he means. But of course it's a tough topic. If measuring bit length of the explanation is a valid way of measuring something's complexity, then the measuring method itself is pretty complex
austincheney 10y ago
I spend nearly all of my effort on "3. Degree of organization." I figure if I can get this right in first the most homoiconic way possible, and secondly with the shortest code possible then I get the first two points mostly for free. It is also why I loathe inheritance. When I read unstructured code written for inheritance I don't see the same path and flow control that the computer sees. I just see a bunch of global classes and public/private/static declarations like a million tiny islands or grains of sand. To me this is a mess.
wessorh 10y ago
https://en.wikipedia.org/wiki/Lacunarity https://en.wikipedia.org/wiki/Lacunarity One of my favorite measures
noway421 10y ago
Cyclomatic complexity might be a go to measure for algorithms.

92 points by breck 10y ago

From the same author this MOOC (Introduction to Information Theory): https://www.complexityexplorer.org/tutorials/55-introduction-to-information-theory https://www.complexityexplorer.org/tutorials/55-introduction... Recommended for (Introduction to Renormalization): https://www.complexityexplorer.org/tutorials/67-introduction-to-renormalization https://www.complexityexplorer.org/tutorials/67-introduction...

stangls 10y ago
Measuring computational complexity with dollars is a time dependent expression of complexity, since that value will change in the future due to cheaper and better hardware. An expression line number of operations or expression via Landau symbols is timeless and can be individually mapped to costs.

mafribe 10y ago

That list is pretty ad-hoc, and doesn't seem to be carefully curated. Fair enough, one has to start somewhere, but ... There is clearly a great deal of overlap, e.g. Minimum Description Length, algorithmic complexity and information theoretic entropy. There are also many well-understood relationships between different forms of complexity, e.g. between space and time complexity. Some appear to be less formal than others, e.g. what is "cost" what is "crypticity"? Finally, regarding the broad distinctions, in what sense are the "difficulty of description" and the "degree of organization" even different?

moxious 10y ago
I think he just didn't define complexity at all, just gave ways of measuring whatever he means. But of course it's a tough topic. If measuring bit length of the explanation is a valid way of measuring something's complexity, then the measuring method itself is pretty complex

austincheney 10y ago

I spend nearly all of my effort on "3. Degree of organization." I figure if I can get this right in first the most homoiconic way possible, and secondly with the shortest code possible then I get the first two points mostly for free. It is also why I loathe inheritance. When I read unstructured code written for inheritance I don't see the same path and flow control that the computer sees. I just see a bunch of global classes and public/private/static declarations like a million tiny islands or grains of sand. To me this is a mess.

wessorh 10y ago

https://en.wikipedia.org/wiki/Lacunarity https://en.wikipedia.org/wiki/Lacunarity One of my favorite measures

noway421 10y ago

Cyclomatic complexity might be a go to measure for algorithms.