{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T06:22:34Z","timestamp":1648880554242},"reference-count":14,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2010,10,27]],"date-time":"2010-10-27T00:00:00Z","timestamp":1288137600000},"content-version":"unspecified","delay-in-days":26,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2010,10]]},"abstract":"<jats:p>We show that, for any abstract complexity measure in the sense of Blum and for any computable function <jats:italic>f<\/jats:italic> (or computable operator <jats:italic>F<\/jats:italic>), the class of problems that are <jats:italic>f<\/jats:italic>-speedable (or <jats:italic>F<\/jats:italic>-speedable) does not have effective measure 0. On the other hand, for sufficiently fast growing <jats:italic>f<\/jats:italic> (or <jats:italic>F<\/jats:italic>), the class of non-speedable computable problems does not have effective measure 0. These results answer some questions raised by Calude and Zimand. We also give a quantitative analysis of Borodin and Trakhtenbrot's Gap Theorem, which corrects a claim by Calude and Zimand.<\/jats:p>","DOI":"10.1017\/s0960129510000174","type":"journal-article","created":{"date-parts":[[2010,10,27]],"date-time":"2010-10-27T07:48:27Z","timestamp":1288165707000},"page":"707-722","source":"Crossref","is-referenced-by-count":1,"title":["Quantitative aspects of speed-up and gap phenomena"],"prefix":"10.1017","volume":"20","author":[{"given":"KLAUS","family":"AMBOS-SPIES","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"THORSTEN","family":"KR\u00c4LING","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2010,10,27]]},"reference":[{"key":"S0960129510000174_ref5","doi-asserted-by":"publisher","DOI":"10.1145\/321679.321691"},{"key":"S0960129510000174_ref14","volume-title":"Computational Complexity: A Quantitative Perspective","author":"Zimand","year":"2006"},{"key":"S0960129510000174_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80030-3"},{"key":"S0960129510000174_ref7","volume-title":"A Quantitative Analysis of the Speed-Up Theorem","author":"Kr\u00e4ling","year":"2008"},{"key":"S0960129510000174_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00023-C"},{"key":"S0960129510000174_ref13","unstructured":"Trakhtenbrot B. A. (1967) Complexity of algorithms and computations. Course Notes, Novosibirsk (in Russian)."},{"key":"S0960129510000174_ref4","doi-asserted-by":"publisher","DOI":"10.1145\/321386.321395"},{"key":"S0960129510000174_ref10","doi-asserted-by":"publisher","DOI":"10.1109\/SWAT.1973.23"},{"key":"S0960129510000174_ref2","first-page":"1","volume-title":"Complexity, Logic and Recursion Theory","author":"Ambos-Spies","year":"1997"},{"key":"S0960129510000174_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00066-6"},{"key":"S0960129510000174_ref1","first-page":"1","volume-title":"Computability, enumerability, unsolvability: Directions in recursion theory","author":"Ambos-Spies","year":"1996"},{"key":"S0960129510000174_ref11","doi-asserted-by":"publisher","DOI":"10.2307\/2272545"},{"key":"S0960129510000174_ref3","first-page":"13","volume-title":"Proc. Sixth Asian Logic Conference 1996","author":"Ambos-Spies","year":"1997"},{"key":"S0960129510000174_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90020-J"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129510000174","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T21:23:42Z","timestamp":1556400222000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129510000174\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,10]]},"references-count":14,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2010,10]]}},"alternative-id":["S0960129510000174"],"URL":"https:\/\/doi.org\/10.1017\/s0960129510000174","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,10]]}}}