I'm sure there are lots of way to define complexity in different

[Cincinnatus]

I'm sure there are lots of way to define complexity in different contexts. Some that I've heard of include:

-Minimum description length / Kolmogorov complexity
-time complexity - number of steps to compute
-parameter complexity - number of parameters needed to specify a model.

There are probably many more... Particularly, there must be some interesting information theoretic ways to talk about this. Does anyone here know about this?

 

[mathwonk]

i love your handle. does everyone know that he was a roman citizen who accepted a high role in the government,perhaps senator or higher, did an outstanding job, and then simply returned to his farm? what a hero. unheard of today, unless maybe sam ervin counts, or jimmy carter.

 

[fleem]

I think ideal compression is the most useful definition. In ideal compression, you aren't dependent on the richness/versatility of the language used to describe the process. It should be noted, also, that there is a difference in compressing a sample of the output of a process, and encoding the process, itself.

 

[CRGreathouse]

Other than space complexity (what is the minimum amount of space needed to computer the answer, not including the input itself) I can't think of anything.

i love your handle. does everyone know that he was a roman citizen who accepted a high role in the government,perhaps senator or higher, did an outstanding job, and then simply returned to his farm? what a hero. unheard of today, unless maybe sam ervin counts, or jimmy carter.

I love Cincinnatus, he's one of my favorite ancient Roman heroes. Horatio (Gaius Horatius) is another; he's the quintessential man's man. He holds the way against hundreds of enemy soldiers while his men, from the other side of the bridge, take it down (at his command) to prevent them from sacking his city; when they collapsed the bridge Horatio, trapped on the wrong side and surrounded by hostiles, swims (in armor!) across to his own people. It was the "Superman" comic book of the early days of the Roman Republic.