Needed: An Empirical Science of Algorithms

Abstract

Deductive algorithmic science has reached a high level of sophistication, but its worst-case and average-case results seldom tell us how well an algorithm is actually going to work in practice. I argue that an empirical science of algorithms is a viable alternative. I respond to misgivings about an empirical approach, including the prevalent notion that only a deductive treatment can be “theoretical” or sophisticated. NP-completeness theory, for instance, is interesting partly because it has significant, if unacknowledged, empirical content. An empirical approach requires not only rigorous experimental design and analysis, but also the invention of empirically-based explanatory theories. I give some examples of recent work that partially achieves this aim.