{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,30]],"date-time":"2023-08-30T08:43:10Z","timestamp":1693384990393},"reference-count":16,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":12245,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1980,9]]},"abstract":"<jats:p>Though researchers in the field of abstract computational complexity theory have utilized many of the tools of recursive function theory in the development of their field, the early results obtained (e.g., see [8]) seemed to be rather independent of results in recursion theory (at least to the extent that the results were not uniformly interesting to both varieties of theorists). It seems to have been generally accepted, however, that strong parallels of one form or another must exist between the two fields. Indeed, recent results of Blum and Marques [7], Morris [13], Soare [15] and Bennison [1], [3] have revealed a striking correspondence between complexity theoretic properties and recursion theoretic properties. These results are not contrived, but rather link together interesting properties which had arisen naturally and independently in their respective fields. This paper presents the results of research aimed at finding a recursion theoretic characterization for a complexity theoretic property which had arisen from the study of the speed-up phenomenon.<\/jats:p><jats:p>In abstract computational complexity theory we are concerned with categorizing computable functions or sets according to their relative difficulty of computation. The phrase \u201cdifficult to compute\u201d may take on different meanings depending on which criteria (complexity theoretic properties) we use to define what it means for a function or set to be hard to compute. In the abstract setting, however, such criteria should yield the same classes of functions or sets regardless of the underlying abstract complexity measure (in the sense of Blum [4], e.g., tape, time, etc.). In other words, such criteria should be measure-independent. In this paper we will be considering one way of defining \u201cdifficult to compute\u201d. Namely, we shall say that a function or set is difficult to compute if it does not have a recursively enumerable complexity sequence as defined by Meyer and Fischer [12]. For a property to have a recursion theoretic characterization it must be measure-independent, for a recursion theoretic property is, by its very nature, measure-independent. It will not be immediately obvious whether or not the property of having an r.e. complexity sequence is measure-independent. We attack this question by first considering an alternative definition of an r.e. complexity sequence, one which is easily seen to be measure-independent.<\/jats:p>","DOI":"10.2307\/2273412","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T21:53:41Z","timestamp":1146952421000},"page":"417-438","source":"Crossref","is-referenced-by-count":3,"title":["Recursively enumerable complexity sequences and measure independence"],"prefix":"10.1017","volume":"45","author":[{"given":"Victor L.","family":"Bennison","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200046430_ref004","doi-asserted-by":"publisher","DOI":"10.1145\/321386.321395"},{"key":"S0022481200046430_ref006","volume-title":"Proceedings of the Courant Computer Science Symposium, No. 7, Computational complexity","author":"Blum","year":"1973"},{"key":"S0022481200046430_ref009","doi-asserted-by":"publisher","DOI":"10.2307\/1970579"},{"key":"S0022481200046430_ref010","doi-asserted-by":"publisher","DOI":"10.1145\/321694.321702"},{"key":"S0022481200046430_ref001","unstructured":"Bennison V. L. , On the computational complexity of recursively enumerable sets, Ph.D. dissertation, University of Chicago, 1976."},{"key":"S0022481200046430_ref012","first-page":"55","volume":"37","author":"Meyer","year":"1972","journal-title":"Computational speed-up by effective operators"},{"key":"S0022481200046430_ref007","first-page":"579","volume":"38","author":"Blum","year":"1973","journal-title":"On complexity properties of recursively enumerable sets"},{"key":"S0022481200046430_ref015","first-page":"545","volume":"42","author":"Soare","year":"1977","journal-title":"Computational complexity, speedable and levelable sets"},{"key":"S0022481200046430_ref005","unstructured":"Blum M. , On defining the complexity of partial recursive functions (unpublished preprint)."},{"key":"S0022481200046430_ref011","unstructured":"Marques I. , Complexity properties of recursively enumerable sets, Ph.D. dissertation, University of California, Berkeley, 1973."},{"key":"S0022481200046430_ref003","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(78)90007-5"},{"key":"S0022481200046430_ref016","volume-title":"Undecidable theories","author":"Tarski","year":"1968"},{"key":"S0022481200046430_ref014","volume-title":"Theory of recursive functions and effective computability","author":"Rogers","year":"1967"},{"key":"S0022481200046430_ref002","volume-title":"Proceedings of the 4th GI Conference on Theoretical Computer Science, Lecture Notes in Computer Science","volume":"67","author":"Bennison","year":"1979"},{"key":"S0022481200046430_ref013","unstructured":"Morris P. H. , Complexity theoretic properties of recursively enumerable sets, Ph.D. dissertation, University of California, Irvine, 1974."},{"key":"S0022481200046430_ref008","doi-asserted-by":"publisher","DOI":"10.1145\/321650.321661"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200046430","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,25]],"date-time":"2019-05-25T21:39:18Z","timestamp":1558820358000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200046430\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1980,9]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1980,9]]}},"alternative-id":["S0022481200046430"],"URL":"https:\/\/doi.org\/10.2307\/2273412","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1980,9]]}}}