Complexity, algorithms, programs, systems: The shifting focus (Q1332328)

From the author's text: ``This abridged text of an invited talk may serve as an editorial introduction to the special issue dedicated to papers presented at the ALCOM Workshop on ``Algorithms: Implementation, Libraries, and Use'' held at Dagstuhl, August 16-18, 1993.'' ``This workshop has shown impressively that enterprising algorithm researchers have embraced systems development as a marketing outlet for our work. This growing emphasis on product orientation is long overdue. I am not saying that we should try to force every theoretical idea into a system. What I have tried to say is that in our work we might profitably distinguish three types of projects, and shift the balance away from an excessive concern with only one or two of these, in particular away from unimplemented algorithms that merely yield asymptotic bounds without any indication that they are practical: 1. The purely theoretical result, packaged in the time-honore mold ``definition-theorem-proof''. Forget software. 2. An algorithm, implemented as a stand-alone ``proof-of- concept-program'' for the primary benefit of the author. As we have heard repeatedly at this workshop, test implementation and test runs often yield profound insights that theory misses. 3. Application systems! With results of types 1 and 2 we may impress our fellow researchers. If we seek an impact beyond our own small circle, we must seize every reasonable opportunuity to turn our work into a product useful to those outside the circle. Such an applications orientation has been a guiding principle for many of the talks at this workshop''.