1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Sep 25, 2007 #1
    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?
  2. jcsd
  3. Sep 25, 2007 #2


    User Avatar
    Science Advisor
    Homework Helper

    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.
  4. Sep 25, 2007 #3
    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.
  5. Sep 25, 2007 #4


    User Avatar
    Science Advisor
    Homework Helper

    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 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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

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