{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,6]],"date-time":"2026-04-06T20:20:38Z","timestamp":1775506838791,"version":"3.50.1"},"reference-count":27,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[1982,1,1]],"date-time":"1982-01-01T00:00:00Z","timestamp":378691200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,18]],"date-time":"2013-07-18T00:00:00Z","timestamp":1374105600000},"content-version":"vor","delay-in-days":11521,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information and Control"],"published-print":{"date-parts":[[1982,1]]},"DOI":"10.1016\/s0019-9958(82)80082-x","type":"journal-article","created":{"date-parts":[[2005,5,6]],"date-time":"2005-05-06T16:43:56Z","timestamp":1115397836000},"page":"8-18","source":"Crossref","is-referenced-by-count":6,"title":["Computational complexity of recursively enumerable sets"],"prefix":"10.1016","volume":"52","author":[{"given":"Robert I.","family":"Soare","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0019-9958(82)80082-X_bib1","doi-asserted-by":"crossref","first-page":"271","DOI":"10.2307\/2270262","article-title":"Recursively enumerable sets which are uniform for finite extensions","volume":"36","author":"Alton","year":"1971","journal-title":"J. Symbol Logic"},{"key":"10.1016\/S0019-9958(82)80082-X_bib2","series-title":"Promptly simple sets and uniformity properties","author":"Ambos-Spies","year":"1982"},{"key":"10.1016\/S0019-9958(82)80082-X_bib3","doi-asserted-by":"crossref","first-page":"417","DOI":"10.2307\/2273412","article-title":"Recursively enumerable complexity sequences and measure independence","volume":"45","author":"Bennison","year":"1980","journal-title":"J. Symbol Logic"},{"key":"10.1016\/S0019-9958(82)80082-X_bib4","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/0304-3975(78)90007-5","article-title":"Some lowness properties and computational complexity sequences","volume":"6","author":"Bennison","year":"1978","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0019-9958(82)80082-X_bib5","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1145\/321637.321648","article-title":"A machine-independent theory of the complexity of recursive functions","volume":"18","author":"Blum","year":"1967","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0019-9958(82)80082-X_bib6","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1145\/321637.321648","article-title":"On effective procedures for speeding up algorithms","volume":"18","author":"Blum","year":"1971","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0019-9958(82)80082-X_bib7","series-title":"Proceedings of the Courant Computer Science Symposium No. 7, Computational Complexity","first-page":"23","article-title":"Some fruitful areas for research into complexity theory","author":"Blum","year":"1973"},{"key":"10.1016\/S0019-9958(82)80082-X_bib8","doi-asserted-by":"crossref","first-page":"579","DOI":"10.2307\/2271984","article-title":"On complexity properties of recursively enumerable sets","volume":"38","author":"Blum","year":"1973","journal-title":"J. Symbol. Logic"},{"key":"10.1016\/S0019-9958(82)80082-X_bib9","first-page":"1143","article-title":"The independence of the continuum hypothesis I","volume":"50","author":"Cohen","year":"1963"},{"key":"10.1016\/S0019-9958(82)80082-X_bib10","doi-asserted-by":"crossref","first-page":"669","DOI":"10.2307\/2272852","article-title":"On subcreative sets and S-reducibility","volume":"39","author":"Gill","year":"1974","journal-title":"J. Symbol. Logic"},{"key":"10.1016\/S0019-9958(82)80082-X_bib11","first-page":"583","article-title":"The halting problem relativized to complements","volume":"41","author":"Hay","year":"1973"},{"key":"10.1016\/S0019-9958(82)80082-X_bib12","first-page":"537","article-title":"Lower bounds for pairs of recursively enumerable degrees","volume":"16","author":"Lachlan","year":"1966"},{"key":"10.1016\/S0019-9958(82)80082-X_bib13","doi-asserted-by":"crossref","first-page":"135","DOI":"10.2140\/pjm.1980.87.135","article-title":"d-simple sets, small sets, and degree classes","volume":"87","author":"Lerman","year":"1980","journal-title":"Pacific J. Math."},{"key":"10.1016\/S0019-9958(82)80082-X_bib14","series-title":"Recursively enumerable generic sets","author":"Maass","year":"1981"},{"key":"10.1016\/S0019-9958(82)80082-X_bib15","article-title":"Characterization of recursively enumerable sets with supersets effectively isomorphic to all recursively enumerable sets","author":"Maass","year":"1982","journal-title":"Trans. Amer. Math. Soc."},{"key":"10.1016\/S0019-9958(82)80082-X_bib16","series-title":"Splitting properties and jump classes","author":"Maass","year":"1981"},{"key":"10.1016\/S0019-9958(82)80082-X_bib17","doi-asserted-by":"crossref","first-page":"529","DOI":"10.2307\/2271777","article-title":"On degrees of unsolvability and complexity properties","volume":"40","author":"Marques","year":"1975","journal-title":"J. Symbol. Logic"},{"key":"10.1016\/S0019-9958(82)80082-X_bib18","doi-asserted-by":"crossref","first-page":"55","DOI":"10.2307\/2272545","article-title":"Computational speed-up by effective operators","volume":"37","author":"Meyer","year":"1972","journal-title":"J. Symbol. Logic"},{"key":"10.1016\/S0019-9958(82)80082-X_bib19","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1090\/S0002-9904-1944-08111-1","article-title":"Recursively enumerable sets of positive integers and their decision problems","volume":"50","author":"Post","year":"1944","journal-title":"Bull. Amer. Math. Soc."},{"key":"10.1016\/S0019-9958(82)80082-X_bib20","series-title":"Theory of recursive functions and effective computability","author":"Rogers","year":"1967"},{"key":"10.1016\/S0019-9958(82)80082-X_bib21","doi-asserted-by":"crossref","first-page":"300","DOI":"10.2307\/1970393","article-title":"The recursively enumerable degrees are dense","volume":"80","author":"Sacks","year":"1963","journal-title":"Ann. of Math."},{"key":"10.1016\/S0019-9958(82)80082-X_bib22","article-title":"Quotient Lattices, index sets, and recursive linear orderings","author":"Schwarz","year":"1982"},{"key":"10.1016\/S0019-9958(82)80082-X_bib23","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1002\/malq.19740201302","article-title":"Relativized halting problems","volume":"20","author":"Selman","year":"1974","journal-title":"Z. Mat. Logik Grundlag. Math."},{"key":"10.1016\/S0019-9958(82)80082-X_bib24","doi-asserted-by":"crossref","first-page":"80","DOI":"10.2307\/1970842","article-title":"Automorphisms of the lattice of recursively enumerable sets. Part I: Maximal sets","volume":"100","author":"Soare","year":"1974","journal-title":"Ann. Math."},{"key":"10.1016\/S0019-9958(82)80082-X_bib25","doi-asserted-by":"crossref","first-page":"545","DOI":"10.2307\/2271876","article-title":"Computational complexity, speedable and levelable sets","volume":"42","author":"Soare","year":"1977","journal-title":"J. Symbol. Logic"},{"key":"10.1016\/S0019-9958(82)80082-X_bib26","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/0003-4843(82)90016-X","article-title":"Automorphisms of the lattice of recursively enumerable sets, Part II: Low sets","volume":"22","author":"Soare","year":"1982","journal-title":"Ann. Math. Logic"},{"key":"10.1016\/S0019-9958(82)80082-X_bib27","doi-asserted-by":"crossref","first-page":"159","DOI":"10.2307\/2269807","article-title":"A minimal pair of r.e. degrees","volume":"31","author":"Yates","year":"1966","journal-title":"J. Symbol. Logic"}],"container-title":["Information and Control"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S001999588280082X?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S001999588280082X?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,2,18]],"date-time":"2019-02-18T03:49:54Z","timestamp":1550461794000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S001999588280082X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1982,1]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1982,1]]}},"alternative-id":["S001999588280082X"],"URL":"https:\/\/doi.org\/10.1016\/s0019-9958(82)80082-x","relation":{},"ISSN":["0019-9958"],"issn-type":[{"value":"0019-9958","type":"print"}],"subject":[],"published":{"date-parts":[[1982,1]]}}}