Measures of model complexity How can we compare complexity of two models with the same number of parameters?
Edit 09/19: To clarify, model complexity is a measure of how hard it is to learn from limited data. When two models fit existing data equally well, a model with lower complexity will give lower error on future data. When approximations are used, this may technically not always be true, but that's OK if it tends to be true in practice. Various approximations give different complexity measures
 A: I think it would depend on the actual model fitting procedure.  For a generally applicable measure, you might consider Generalized Degrees of Freedom described in Ye 1998 -- essentially the sensitivity of change of model estimates to perturbation of observations -- which works quite well as a measure of model complexity.
A: Minimum Description Length (MDL) and Minimum Message Length (MML) are certainly worth checking out.
As far as MDL is concerned, a simple paper that illustrates the Normalized Maximum Likelihood (NML) procedure as well as the asymptotic approximation is:

S. de Rooij & P. Grünwald. An empirical
  study of minimum description length
  model selection with infinite
  parametric complexity.  Journal of
  Mathematical Psychology, 2006, 50,
  180-192

Here, they look at the model complexity of a Geometric vs. a Poisson distribution. An excellent (free) tutorial on MDL can be found here.
Alternatively, a paper on the complexity of the exponential distribution examined with both MML and MDL can be found here. Unfortunately, there is no up-to-date tutorial on MML, but the book is an excellent reference, and highly recommended.
A: Minimum Description Length may be an avenue worth pursuing.
A: By "model complexity" one usually means the richness of the model space. Note that this definition does not depend on data. For linear models, the richness of the model space is trivially measured with the diminution of the space. This is what some authors call the "degrees of freedom" (although historically, the degrees-of-freedom was reserved for the difference between the model space and the sample space). 
For non linear models, quantifying the richness of the space is less trivial. The Generalized Degrees of Freedom (see ars's reply) is such a measure. It is indeed very general and can be used for any "weird" model space such as trees, KNN, and the likes. 
The VC dimension  is another measure.  
As mentioned above, this definition of "complexity" is data independent. So two models with the same number of parameters will typically have the same "complexity". 
A: Besides the various measures of Minimum Description Length (e.g., normalized maximum likelihood, Fisher Information approximation), there are two other methods worth to mention:  


*

*Parametric Bootstrap. It's a lot easier to implement than the demanding MDL measures. A nice paper is by Wagenmaker and colleagues:
Wagenmakers, E.-J., Ratcliff, R., Gomez, P., & Iverson, G. J. (2004). Assessing model mimicry using the parametric bootstrap. Journal of Mathematical Psychology, 48, 28-50.
The abstract:

We present a general sampling
  procedure to quantify model mimicry,
  defined as the ability of a model to
  account for data generated by a
  competing model. This sampling
  procedure, called the parametric
  bootstrap cross-fitting method (PBCM;
  cf. Williams (J. R. Statist. Soc. B 32
  (1970) 350; Biometrics 26 (1970) 23)),
  generates distributions of differences
  in goodness-of-fit expected under each
  of the competing models. In the data
  informed version of the PBCM, the
  generating models have specific
  parameter values obtained by fitting
  the experimental data under
  consideration. The data informed
  difference distributions can be
  compared to the observed difference in
  goodness-of-fit to allow a
  quantification of model adequacy. In
  the data uninformed version of the
  PBCM, the generating models have a
  relatively broad range of parameter
  values based on prior knowledge.
  Application of both the data informed
  and the data uninformed PBCM is
  illustrated with several examples.  

Update: Assessing model mimicry in plain English. You take one of the two competing models and randomly pick a set of parameters for that model (either data informed or not). Then, you produce data from this model with the picked set of parameters. Next, you let both models fit the produced data and check which of the two candidate models gives the better fit. If both models are equally flexible or complex, the model from which you produced the data should  give a better fit. However, if the other model is more complex, it could give a better fit, although the data was produced from the other model. You repeat this several times with both models (i.e., let both models produce data and look which of the two fits better). The model that "overfits" the data produced by the other model is the more complex one.

*Cross-Validation: It is also quite easy to implement. See the answers to this question. However, note that the issue with it is that the choice among the sample-cutting rule (leave-one-out, K-fold, etc) is an unprincipled one. 
A: From Yaroslav's comments to Henrik's answer:
but cross-validation seems to just postpone the task of assessing complexity. If you use data to pick your parameters and your model as in cross-validation, the relevant question becomes how estimate the amount of data needed for this "meta"-fitter to perform well 
I wonder whether this is not in itself informative. You perform several $k$-fold CV with varying $k$ (say along a grid) and look which model performs better as $k$ increases. More specifically: I wonder whether any differentiation among the two model in there $CV(k)$ performance as a function of $k$ can be taken as evidence that this model (the one whose relative performance decreases less when $k$ increases) would be the less complex one.
You could even give a 'significance' flavor to this since the result of the procedure is directly in terms (units) of difference in out of sample forecasting error.
A: What about the information criterion for model comparison?
See e.g. http://en.wikipedia.org/wiki/Akaike_information_criterion
Model complexity is here the number of parameters of the model.
