One of the first things here is about the relationship between problem complexity and solution complexity. But how is this complexity measured empirically?
We have the notion of cyclomatic complexity, an empirical measurement that can be used to assess the complexity of a piece of code, and presumably that code is the solution to a problem. So, OK, we have something like a measurement of solution complexity, but how is problem complexity measured, and what is its empirical relationship to the measure of complexity of the solution? Hell, what are the units we would measure such complexity, even?
I think people who do what we do have a certain insecurity about how much of what we do is decidedly not science. And we have this tendency to talk in science-y ways about what we do, which sound good to our ears, but aren't quite rooted in anything concrete.
The problem with cyclomatic complexity measurements, is that if you take two similar pieces of code, one with error handling for all potential failures, and one with absolutely no errors handling you get a large variation in the resulting complexity metric. Both pieces of code will probably pass simple correctness tests. But you can't really even make a statement about which is more robust, as the code with all the error handling paths may be full of latent bugs of worse severity than (another thing hard to quantify) simply not handling the errors.
So, when people start talking about the cyclomatic complexity, it seems to me that we are better off understanding we are deep into a philosophical discussion rather than a scientific one.
We found that due mostly to issues regarding population variance, that the linearity of the relationship between these two measurements has been severely un-derestimated. Using modern statistical tools we develop linear models that can account for the majority of CC by LOC alone. We conclude that CC has no explanatory power of its own and that LOC and CC measure the same property. We also conclude that if CC does have any validity as a measure of either complexity or test space size, then we must conclude these factors grow linearly with size regardless of software language, paradigm, or methodology.
I was looking for another reference, and I found this one, which seems far better researched.
You can estimate complexity by the time to add or fix functionality in that part of the code. That's pretty much why you're measuring complexity in the first place. So you know if you're hemoraging or not.
