Hostname: page-component-8448b6f56d-qsmjn Total loading time: 0 Render date: 2024-04-25T05:18:46.078Z Has data issue: false hasContentIssue false
  • English
  • Français

Computational complexity, speedable and levelable sets1

Published online by Cambridge University Press:  12 March 2014

Robert I. Soare
Robert I. Soare*
Affiliation:
University of Chicago, Chicago, Illinois 60637
Get access Rights & Permissions [Opens in a new window]

Extract

One of the most interesting aspects of the theory of computational complexity is the speed-up phenomenon such as the theorem of Blum [6, p. 326] which asserts the existence of a 0, 1-valued total recursive function with arbitrarily large speed-up. Blum and Marques [10] extended the speed-up definitions from total to partial recursive functions, or equivalently, to recursively enumerable (r.e.) sets, and introduced speedable and levelable sets. They classified the effectively speedable sets as the subcreative sets but remarked that “the characterizations we provided for speedable and levelable sets do not seem to bear a close relationship to any already well-studied class of recursively enumerable sets.” The purpose of this paper is to give an “information theoretic” characterization of speedable and levelable sets in terms of index sets resembling the jump operator. From these characterizations we derive numerous consequences about the degrees and structure of speedable and levelable sets.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 42 , Issue 4 , December 1977 , pp. 545 - 563
Copyright
Copyright © Association for Symbolic Logic 1977

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 National Science Foundation Grants G P 19958 and MPS 75-06888. We are grateful to D. A. Alton for several corrections and suggestions and to G. Riccardi for pointing out corrections and misprints.

References

REFERENCES

[1]Alton, D. A., Recursively enumerable sets which are uniform for finite extensions, this Journal, vol. 36 (1971), pp. 271–287.Google Scholar
[2]Bennison, V. L., Recursively enumerable complexity sequences. Part I, Notices of the American Mathematical Society, vol. 22 (1975), p. A–643.Google Scholar
[3]Bennison, V. L., Recursively enumerable complexity sequences. Part II, Notices of the American Mathematical Society, vol. 23 (1976), p. A–19.Google Scholar
[4]Bennison, V. L., On the computational complexity of recursively enumerable sets, Ph.D. Dissertation, University of Chicago, 1976.Google Scholar
[5]Bennison, V. L. and Soare, R. I., Some lowness properties and computational complexity sequences (to appear).Google Scholar
[6]Blum, M., A machine-independent theory of the complexity of recursive functions, Journal of the Association for Computing Machinery, vol. 14 (1967), pp. 322–336.CrossRefGoogle Scholar
[7]Blum, M., On effective procedures for speeding up algorithms, Journal of the Association for Computing Machinery, vol. 18 (1971), pp. 290–305.CrossRefGoogle Scholar
[8]Blum, M., Subcreative sets and complexity of algorithms, unpublished preprint, 1971.Google Scholar
[9]Blum, M. and Gill, J., Some fruitful areas for research into complexity theory, Proceedings of the Courant Computer Science Symposium No. 7, Computational complexity (Rustin, R., Editor), Algorithmics Press, New York, 1973, pp. 23–36.Google Scholar
[10]Blum, M. and Marques, I., On complexity properties of recursively enumerable sets, this Journal, vol. 38 (1973), pp. 579–593.Google Scholar
[11]Filotti, I., On effectively levelable sets, Recursive Function Theory Newsletter, 2 (1972), pp. 12–13.Google Scholar
[12]Gill, J. and Morris, P., On subcreative sets and S-reducibility, this Journal, vol. 39 (1974), pp. 669–677.Google Scholar
[13]Hay, L., The halting problem relativized to complements, Proceedings of the American Mathematical Society, vol. 41 (1973), pp. 583–587.CrossRefGoogle Scholar
[14]Blum, M., The class of recursively enumerable subsets of a recursively enumerable set, Pacific Journal of Mathematics, vol. 46 (1973), pp. 167–183.Google Scholar
[15]Blum, M., Spectra and the halting problem, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 21 (1975), pp. 167–176.Google Scholar
[16]Jockusch, C. G. Jr., The degrees of hyperhyperimmune sets, this Journal, vol. 34 (1969), pp. 489–493.Google Scholar
[17]Jockusch, C. G., Relationships between reducibilities, Transactions of the American Mathematical Society, vol. 142 (1969), pp. 229–237.CrossRefGoogle Scholar
[18]Lachlan, A. H., The elementary theory of recursively enumerable sets, Duke Mathematical Journal, vol. 35 (1968), pp. 123–146.CrossRefGoogle Scholar
[19]Jockusch, C. G., On the lattice of recursively enumerable sets, Transactions of the American Mathematical Society, vol. 130 (1968), pp. 1–37.Google Scholar
[20]Lachlan, A. H., Degrees of recursively enumerable sets which have no maximal superset, this Journal, vol. 33 (1968), pp. 431–443.Google Scholar
[21]Landweber, L. H. and Robertson, E. L., Recursive properties of abstract complexity classes, Journal of the Association for Computing Machinery, vol. 19 (1972), pp. 296–308.CrossRefGoogle Scholar
[22]Marques, I., Complexity properties of the recursively enumerable sets, Ph.D. Dissertation, University of California, Berkeley, 1973.Google Scholar
[23]Marques, I., On degrees of unsolvability and complexity properties, this Journal, vol. 40 (1975), pp. 529–540.Google Scholar
[24]Martin, D. A., Classes of recursively enumerable sets and degrees of unsolvability, Zeilschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 12 (1966), pp. 295–310.CrossRefGoogle Scholar
[25]Meyer, A. R. and Fischer, P. C., Computational speed-up by effective operators, this Journal, vol. 37 (1972), pp. 55–68.Google Scholar
[26]Morris, P. H., Complexity theoretic properties of recursively enumerable sets, Ph.D. Dissertation, University of California, Irvine, 1974.Google Scholar
[27]Post, E. L., Recursively enumerable sets of positive integers and their decision problems, Bulletin of the American Mathematical Society, vol. 50 (1944), pp. 284–316.CrossRefGoogle Scholar
[28]Robinson, R. W., The inclusion lattice and degrees of unsolvability of the recursively enumerable sets, Ph.D. Dissertation, Cornell University, 1966.Google Scholar
[29]Robinson, R. W., A dichotomy of the recursively enumerable sets, Zeilschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 14 (1968), pp. 339–356.CrossRefGoogle Scholar
[30]Robinson, R. W., Interpolation and embedding in the recursively enumerable degrees, Annals of Mathematics, vol. 93 (1971), pp. 285–314.CrossRefGoogle Scholar
[31]Rogers, H. Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[32]Sacks, G. E., Recursive enumerability arid the jump operator, Transactions of the American Mathematical Society, vol. 108 (1963), pp. 223–229.CrossRefGoogle Scholar
[33]Sacks, G. E., Degrees of unsolvability, revised edition, Annals of Mathematics Studies, no. 55, Princeton University Press, Princeton, N. J., 1966.Google Scholar
[34]Selman, A. L., Relativized halting problems, Zeilschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 20 (1974), pp. 193–198.CrossRefGoogle Scholar
[35]Shoenfield, J. R., Degrees of unsolvability, North-Holland, Amsterdam, 1971.Google Scholar
[36]Shoenfield, J. R., Degrees of classes of RE sets, this Journal, vol. 41 (1976), pp. 695–696.Google Scholar
[37]Soare, R. I., Automorphisms of the lattice of recursively enumerable sets, Bulletin of the American Mathematical Society, vol. 80 (1974), pp. 53–58.CrossRefGoogle Scholar
[38]Soare, R. I., Automorphisms of the lattice of recursively enumerable sets. Part I: Maximal sets, Annals of Mathematics, vol. 100 (1974), pp. 80–120.CrossRefGoogle Scholar
[39]Soare, R. I., The infinite injury priority method, this Journal, vol. 41 (1976), pp. 513–530.Google Scholar
[40]Soare, R. I., Automorphisms of the lattice of recursively enumerable sets. Part II: Low sets (to appear).Google Scholar
[41]Soare, R. I., Automorphisms of the lattice of recursively enumerable sets. Part III: Complete sets (in preparation).Google Scholar
[42]Tulloss, R. E., Some complexities of simplicity: concerning grades of simplicity of recursively enumerable sets, Ph.D. Dissertation, University of California, Berkeley, 1971.Google Scholar
[43]Boas, P. van Emde, Ten years of speedup, Mathematical Foundations of Computer Science 4th Symposium, Mariánske Lázně, 1975, Lecture Notes in Computer Science, No. 32 (1975), pp. 13–29.Google Scholar
[44]Yates, C. E. M., Three theorems on the degree of recursively enumerable sets, Duke Mathematical Journal, vol. 32 (1965), pp. 461–468.CrossRefGoogle Scholar