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

  • #1
389
0
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?
 

Answers and Replies

  • #2
mathwonk
Science Advisor
Homework Helper
2020 Award
11,093
1,295
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.
 
  • #3
437
0
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.
 
  • #4
CRGreathouse
Science Advisor
Homework Helper
2,820
0
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.
 

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

Replies
12
Views
179
Replies
11
Views
2K
Replies
7
Views
675
Replies
11
Views
2K
  • Last Post
Replies
3
Views
2K
Replies
3
Views
927
  • Last Post
Replies
5
Views
2K
Replies
6
Views
12K
Replies
7
Views
905
Top