Research Talk: An Intersection of Software Engineering and Complexity Theory

Abstract

In 2001, J. P. Lewis published an article (ACM SEN) that claimed there are hard limits on our ability to estimate software development time. His argument is based on the notion of? algorithmic complexity?, which is a measure of the shortest program that will produce a given string. He noted that this problem is unsolvable in general. Lewis showed that a software requirement specification can be recast as a string, and then argued that since we cannot find the shortest program to produce that string, we cannot accurately estimate software development times.

In this talk, I review Lewis’s article and critique his conclusions. I find that he is technically correct, in a narrow sense, but misses important aspects of the software development process, especially the estimation task. I then extend his general idea to include other methods in the complexity theory? toolbox? and consider whether they might apply to other questions within software engineering.

This work expands an article I published in 2002.