{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,6]],"date-time":"2026-04-06T19:53:12Z","timestamp":1775505192985,"version":"3.50.1"},"reference-count":44,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":13250,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1977,12]]},"abstract":"<jats:p>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 <jats:italic>partial<\/jats:italic> 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 \u201cthe 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.\u201d The purpose of this paper is to give an \u201cinformation theoretic\u201d 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.<\/jats:p>","DOI":"10.2307\/2271876","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T17:45:39Z","timestamp":1146937539000},"page":"545-563","source":"Crossref","is-referenced-by-count":47,"title":["Computational complexity, speedable and levelable sets"],"prefix":"10.1017","volume":"42","author":[{"given":"Robert I.","family":"Soare","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200050179_ref042","unstructured":"Tulloss R. E. , Some complexities of simplicity: concerning grades of simplicity of recursively enumerable sets, Ph.D. Dissertation, University of California, Berkeley, 1971."},{"key":"S0022481200050179_ref040","unstructured":"Soare R. I. , Automorphisms of the lattice of recursively enumerable sets. Part II: Low sets (to appear)."},{"key":"S0022481200050179_ref039","first-page":"513","volume":"41","author":"Soare","year":"1976","journal-title":"The infinite injury priority method"},{"key":"S0022481200050179_ref038","doi-asserted-by":"publisher","DOI":"10.2307\/1970842"},{"key":"S0022481200050179_ref036","first-page":"695","volume":"41","author":"Shoenfield","year":"1976","journal-title":"Degrees of classes of RE sets"},{"key":"S0022481200050179_ref035","volume-title":"Degrees of unsolvability","author":"Shoenfield","year":"1971"},{"key":"S0022481200050179_ref033","volume-title":"Annals of Mathematics Studies","author":"Sacks","year":"1966"},{"key":"S0022481200050179_ref032","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1963-0155747-3"},{"key":"S0022481200050179_ref031","volume-title":"Theory of recursive functions and effective computability","author":"Rogers","year":"1967"},{"key":"S0022481200050179_ref029","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19680142105"},{"key":"S0022481200050179_ref028","unstructured":"Robinson R. W. , The inclusion lattice and degrees of unsolvability of the recursively enumerable sets, Ph.D. Dissertation, Cornell University, 1966."},{"key":"S0022481200050179_ref026","unstructured":"Morris P. H. , Complexity theoretic properties of recursively enumerable sets, Ph.D. Dissertation, University of California, Irvine, 1974."},{"key":"S0022481200050179_ref024","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19660120125"},{"key":"S0022481200050179_ref022","unstructured":"Marques I. , Complexity properties of the recursively enumerable sets, Ph.D. Dissertation, University of California, Berkeley, 1973."},{"key":"S0022481200050179_ref027","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1944-08111-1"},{"key":"S0022481200050179_ref021","doi-asserted-by":"publisher","DOI":"10.1145\/321694.321702"},{"key":"S0022481200050179_ref002","first-page":"A","article-title":"Recursively enumerable complexity sequences. Part I","volume":"22","author":"Bennison","year":"1975","journal-title":"Notices of the American Mathematical Society"},{"key":"S0022481200050179_ref023","first-page":"529","volume":"40","author":"Marques","year":"1975","journal-title":"On degrees of unsolvability and complexity properties"},{"key":"S0022481200050179_ref044","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-65-03247-3"},{"key":"S0022481200050179_ref020","first-page":"431","volume":"33","author":"Lachlan","year":"1968","journal-title":"Degrees of recursively enumerable sets which have no maximal superset"},{"key":"S0022481200050179_ref030","doi-asserted-by":"publisher","DOI":"10.2307\/1970776"},{"key":"S0022481200050179_ref043","first-page":"13","volume-title":"Mathematical Foundations of Computer Science 4th Symposium","author":"Boas","year":"1975"},{"key":"S0022481200050179_ref011","first-page":"12","article-title":"On effectively levelable sets","volume":"2","author":"Filotti","year":"1972","journal-title":"Recursive Function Theory Newsletter"},{"key":"S0022481200050179_ref004","unstructured":"Bennison V. L. , On the computational complexity of recursively enumerable sets, Ph.D. Dissertation, University of Chicago, 1976."},{"key":"S0022481200050179_ref003","first-page":"A","article-title":"Recursively enumerable complexity sequences. Part II","volume":"23","author":"Bennison","year":"1976","journal-title":"Notices of the American Mathematical Society"},{"key":"S0022481200050179_ref041","unstructured":"Soare R. I. , Automorphisms of the lattice of recursively enumerable sets. Part III: Complete sets (in preparation)."},{"key":"S0022481200050179_ref034","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19740201302"},{"key":"S0022481200050179_ref008","unstructured":"Blum M. , Subcreative sets and complexity of algorithms, unpublished preprint, 1971."},{"key":"S0022481200050179_ref006","doi-asserted-by":"publisher","DOI":"10.1145\/321386.321395"},{"key":"S0022481200050179_ref025","first-page":"55","volume":"37","author":"Meyer","year":"1972","journal-title":"Computational speed-up by effective operators"},{"key":"S0022481200050179_ref016","first-page":"489","volume":"34","author":"Jockusch","year":"1969","journal-title":"The degrees of hyperhyperimmune sets"},{"key":"S0022481200050179_ref037","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1974-13350-1"},{"key":"S0022481200050179_ref019","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/S0002-9947-1968-0227009-1","article-title":"On the lattice of recursively enumerable sets","volume":"130","author":"Jockusch","year":"1968","journal-title":"Transactions of the American Mathematical Society"},{"key":"S0022481200050179_ref013","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1973-0327495-X"},{"key":"S0022481200050179_ref001","first-page":"271","volume":"36","author":"Alton","year":"1971","journal-title":"Recursively enumerable sets which are uniform for finite extensions"},{"key":"S0022481200050179_ref005","unstructured":"Bennison V. L. and Soare R. I. , Some lowness properties and computational complexity sequences (to appear)."},{"key":"S0022481200050179_ref007","doi-asserted-by":"publisher","DOI":"10.1145\/321637.321648"},{"key":"S0022481200050179_ref009","first-page":"23","volume-title":"Proceedings of the Courant Computer Science Symposium No. 7, Computational complexity","author":"Blum","year":"1973"},{"key":"S0022481200050179_ref012","first-page":"669","volume":"39","author":"Gill","year":"1974","journal-title":"On subcreative sets and S-reducibility"},{"key":"S0022481200050179_ref014","doi-asserted-by":"crossref","first-page":"167","DOI":"10.2140\/pjm.1973.46.167","article-title":"The class of recursively enumerable subsets of a recursively enumerable set","volume":"46","author":"Blum","year":"1973","journal-title":"Pacific Journal of Mathematics"},{"key":"S0022481200050179_ref015","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1002\/malq.19750210122","article-title":"Spectra and the halting problem","volume":"21","author":"Blum","year":"1975","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"S0022481200050179_ref010","first-page":"579","volume":"38","author":"Blum","year":"1973","journal-title":"On complexity properties of recursively enumerable sets"},{"key":"S0022481200050179_ref017","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1969-0245439-X"},{"key":"S0022481200050179_ref018","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-68-03513-8"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200050179","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T16:46:33Z","timestamp":1558975593000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200050179\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1977,12]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1977,12]]}},"alternative-id":["S0022481200050179"],"URL":"https:\/\/doi.org\/10.2307\/2271876","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1977,12]]}}}