On effective procedures for speeding up algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On effective procedures for speeding up algorithms

Full text

Pdf (697 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the first annual ACM symposium on Theory of computing table of contents

Marina del Rey, California, United States

Pages: 43 - 53

Year of Publication: 1969

Author

Manuel Blum

Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, California

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 19, Citation Count: 5

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/800169.805420 What is a DOI?

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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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.

CITED BY 5

	Giorgio Ausiello, On bounds on the number of steps to compute functions, Proceedings of the second annual ACM symposium on Theory of computing, p.41-47, May 04-06, 1970, Northampton, Massachusetts, United States
	J. Hartmanis , J. E. Hopcroft, An Overview of the Theory of Computational Complexity, Journal of the ACM (JACM), v.18 n.3, p.444-475, July 1971
	Robert L. Constable , Allan B. Borodin, Subrecursive Programming Languages, Part I: efficiency and program structure, Journal of the ACM (JACM), v.19 n.3, p.526-568, July 1972
	R. L. Constable , J. Hartmanis, Complexity of formal translations and speed-up results, Proceedings of the third annual ACM symposium on Theory of computing, p.244-250, May 03-05, 1971, Shaker Heights, Ohio, United States
	Andy N. C. Kang, On the complexity of proving functions, Proceedings of the November 16-18, 1971, fall joint computer conference, November 16-18, 1971, Las Vegas, Nevada