I am a great fan of constructive applications of Kolmogorov complexity, but I do believe that your application is 'a bridge too far'. It is very creative though.
For example, take the Busy Beaver problem. (see http://www.drb.insel.de/~heiner/BB/bb-6list) The contenders to solving specific instances are as close as we can get to minimal size programs. However a minimal size BB-contender takes 3.0*10^1730 steps to write 1.2*10^865 ones on a tape. There are slightly longer programs that do the same job in less time.
Furthermore there is a problem of semantics. What is a program supposed to do? Kolmogorov complexity does not help here.
The paper 'Large Limits to Software Estimation' intermingles program size and minimal program size. The latter can not be created/computed within reasonable time.
So, in general, the time necessary to program a piece of software of minimal size is well-known. Thanks to Kolmogorov complexity.
As far as I know there are no specific K-complexity proofs about the (time/space) complexity of programs larger than minimal size.
This invalidates the conclusions in the paper. So keep on creating and testing software metrics!
Slashdot Mirror
For example, take the Busy Beaver problem. (see http://www.drb.insel.de/~heiner/BB/bb-6list) The contenders to solving specific instances are as close as we can get to minimal size programs. However a minimal size BB-contender takes 3.0*10^1730 steps to write 1.2*10^865 ones on a tape. There are slightly longer programs that do the same job in less time.
Furthermore there is a problem of semantics. What is a program supposed to do? Kolmogorov complexity does not help here.
So, in general, the time necessary to program a piece of software of minimal size is well-known. Thanks to Kolmogorov complexity.
As far as I know there are no specific K-complexity proofs about the (time/space) complexity of programs larger than minimal size.
This invalidates the conclusions in the paper. So keep on creating and testing software metrics!