Hostname: page-component-8448b6f56d-tj2md Total loading time: 0 Render date: 2024-04-24T04:22:50.043Z Has data issue: false hasContentIssue false
  • English
  • Français

Diversity of speed-ups and embeddability in computational complexity1

Published online by Cambridge University Press:  12 March 2014

Donald A. Alton
Donald A. Alton*
Affiliation:
University of Iowa, Iowa City, Iowa 52242
Get access Rights & Permissions [Opens in a new window]

Extract

The theory of computational complexity deals with those functions which can be computed subject to certain restrictions on the resources (for instance, time or memory) available for computation. Blum [5] gave an axiomatic characterization of some of the properties which should be possessed by a measure of computational complexity and established the existence of speed-upable functions—computable functions which fail to possess optimal programs in a particularly strong sense. Recursion theorists tend to like such functions, and people concerned with the specifics of real computing tend to consider such functions somewhat pathological. In Theorem 2 we show that such pathology is rampant: there is a great diversity of behavior among the collections of “run-times” of different functions which do not possess optimal programs, where such diversity is gauged by certain algebraic criteria which have computational significance. Roughly speaking, these algebraic criteria concern the ways in which various functions can be intermixed to satisfy requirements that certain functions can or cannot be computed more easily than certain other functions. (More detailed motivation for the relevance of these algebraic notions is given later.) Specifically, in Theorem 2 we generalize the embeddability theorem of McCreight and Meyer [12] (discussed below) by making speed-upable functions responsible for the embedding.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 41 , Issue 1 , March 1976 , pp. 199 - 214
Copyright
Copyright © Association for Symbolic Logic 1976

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

1

This research was supported by NSF grant GJ-33168. The results were announced and discussed at the Symposium on Algorithms and their Complexity at the Mathematisches Forschungsinstitut, Oberwolfach, Germany, in November 1972. Transportation to that conference was provided by NSF grant GJ-36148. The manuscript was revised during May, 1974, when the author was supported by an Old Gold Summer Faculty Research Fellowship awarded by the University of Iowa.

References

BIBLIOGRAPHY

[1] Alton, Donald A., Diversity of speed-ups and embeddability, Notices of the American Mathematical Society, vol. 19 (1972), A–711.Google Scholar
[2] Alton, Donald A., Operator embeddability in computational complexity, Notices of the American Mathematical Society, vol. 19 (1972), A–763.Google Scholar
[3] Alton, Donald A., Diversity of speed-ups and embeddability in computational complexity, Technical Report 73-01, Department of Computer Science, University of Iowa, 01 1973; available as Report NSF-OCA-GJ-33168-01 (accession no. PB-221089) from National Technical Infor-mation Service, U.S. Department of Commerce, Springfield, Va. 22151.Google Scholar
[4] Alton, Donald A. and Madison, E. W., Computability of Boolean algebras and their extensions, Annals of Mathematical Logic, vol. 6 (1973), pp. 95–128.CrossRefGoogle Scholar
[5] Blum, Manuel, A machine-independent theory of complexity of recursive functions, Journal of the Association for Computing Machinery, vol. 14 (1967), pp. 322–336.CrossRefGoogle Scholar
[6] Borodin, A., Computational complexity and the existence of complexity gaps, Journal of the Association for Computing Machinery, vol. 19 (1972), pp. 158–174.CrossRefGoogle Scholar
[7] Constable, Robert L., The operator gap, Journal of the Association for Computing Machinery, vol. 19 (1972), pp. 175–183.CrossRefGoogle Scholar
[8] Davis, Martin, Computability and unsolvability, McGraw-Hill, New York, 1958.Google Scholar
[9] Feiner, L., Orderings and Boolean algebras not isomorphic to recursive ones, Ph.D. Thesis, Massachusetts Institute of Technology, Cambridge, Mass., 1967.Google Scholar
[10] Fröhlich, A. and Sheperdson, J. C., Effective procedures in field theory, Transactions of the Royal Philosophical Society of London, Series A, vol. 248 (1956), pp. 407–432.Google Scholar
[11] McCreight, Edward M., Classes of computable functions defined by bounds on computation, Ph.D. Thesis, Carnegie-Mellon University, Pittsburgh, Penn., 1969.CrossRefGoogle Scholar
[12] McCreight, Edward M. and Meyer, A. R., Classes of computable functions defined by bounds on computation: preliminary report, Conference Record of the Association for Computing Machinery Symposium on Theory of Computing, Association for Computing Machinery, New York, 1969, pp. 79–88.Google Scholar
[13] Meyer, Albert R. and Fischer, Patrick C., Computational speed-up by effective operators, this Journal, vol. 37 (1972), pp. 55–68.Google Scholar
[14] Mostowski, A., Über gewisse universelle Relationen, Annales de la Société Polonaise de Mathématique, vol. 17 (1938), pp. 117–118.Google Scholar
[15] Rabin, M. O., Computable algebra, Transactions of the American Mathematical Society, vol. 95 (1960), pp. 341–360.Google Scholar
[16] Rogers, H. Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[17] Rogers, H. Jr., Gödel numberings of partial recursive functions, this Journal, vol. 23 (1958), pp. 331–341.Google Scholar
[18] Sacks, G. E., Degrees of unsolvability, Annals of Mathematical Studies, no. 55, Princeton, N.J., 1963.Google Scholar
[19] Schnorr, C. P., Rekursive Funktionen und Komplexitätstheorie, Teubner-Verlag, Stuttgart (to appear).Google Scholar
Alton, Donald A., Non-existence of program optimizers in an abstract setting, Journal of Computer and Systems Sciences (to appear). This is a revised version of Technical Report 73-08, Department of Computer Science, University of Iowa, available as Report NSF-OCA-GJ-33168-02 (accession number PB-226 464/AS) from National Technical Information Service, U.S. Department of Commerce, Springfield, Va. 22151.Google Scholar
Alton, Donald A., Iterated quotients of the lattice of recursively enumerable sets, Proceedings of the London Mathematical Society (3), vol. 28 (1974), pp. 1–12.CrossRefGoogle Scholar
Bass, Leonard and Young, Paul, Ordinal hierarchies and naming complexity classes, Journal of the Association for Computing Machinery, vol. 20 (1973), pp. 668–686.CrossRefGoogle Scholar
Borodin, Allan, Computational complexity: theory and practice, Currents in the theory of computing (Aho, Alfred V., Editor), Prentice-Hall, Englewood Cliffs, N.J., 1973, pp. 35–89.Google Scholar
Hartmanis, Juris and Hopcroft, John, An overview of the theory of computational complexity, Journal of the Association for Computing Machinery, vol. 18 (1971), pp. 444–475.CrossRefGoogle Scholar
Machtey, Michael, Augmented loop languages and classes of computable functions, Journal of Computer and System Sciences, vol. 6 (1972), pp. 603–624.CrossRefGoogle Scholar
Moll, Robert, An operator embedding theorem for complexity classes of recursive functions, MAC Technical Memorandum 32, Project MAC, M.I.T., Cambridge, Mass., 05 1973 Theoretical Computer Science (to appear).Google Scholar