Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

This paper is concerned with the nature of speedups. Let f be any recursive function. We show that there is no effective procedure for going from an algorithm for f to a significantly faster algorithm for f. On the other hand, there is an effective procedure for going from any algorithm to a faster algorithm, provided one has a bound on the size of the algorithm that does the computation faster for all inputs. If no bound on the size of the faster algorithm is known in advance, one can still obtain a pseudo speedup: This is a very fast algorithm which computes a variant of the function, one which differs from the original function on a finite number of inputs.

REFERENCES

• 1: Manuel Blum, A Machine-Independent Theory of the Complexity of Recursive Functions, Journal of the ACM (JACM), v.14 n.2, p.322-336, April 1967 [doi>10.1145/321386.321395]
• 2: Ritchie, D. M., "Program Structure and Computational Complexity", Thesis, Harvard University (1968).
• 3: Hartmanis, J., and Stearns, R. E., "On The Computational Complexity of Algorithms", Trans. of the AMS, Vol. 117, No. 5, (May 1965), 285-306.
• 4: Meyer, A. R., and Fischer, P. C., "On Computational Speedup," Tech. Report of the Carnegie-Mellon University, Department of Computer Science (May 1968), 21 pp./IEEE Conference Record Ninth Annual Symposium on Switching and Automata Theory (October 1968), 351-355.
• 5: Rogers, H., Jr. "Gödel Numberings of Partial Recursive Functions," Journal of Symbolic Logic, Vol. 23, No. 3 (September 1958), 331-341.
• 6: Hartley Rogers, Jr., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, 1987
• 7: Young, P. R., "Toward a Theory of Enumerations", IEEE Conference Record Ninth Annual Symposium on Switching and Automata Theory (October 1968), 334-350.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Relations among complexity classes

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Recursive function theory; Computability theory

General Terms:
Algorithms, Theory