1Program Speedups in Theory and Practice

The aim of this discussion paper is to stimulate (or perhaps to provoke) stronger in-teractions among theoreticians and practitioners interested in efficient problem solutions. We emphasize computing abilities in relation to programming and specification languages, as these provide the user’s interface with the computer. Due to the breadth of the topic we mainly discuss efficiency as measured by computation time, ignoring space and other measures; and this on sequential, deterministic, individual, and fixed computers, not treating parallelism, stochastic algorithms, distributed comput-ing, or dynamically expanding architectures