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?