Quantitative aspects of speed-up and gap phenomena

• Verfasst von: Ambos-Spies, Klaus [VerfasserIn]
• Verfasst von: Kräling, Thorsten [VerfasserIn]
• Titel: Quantitative aspects of speed-up and gap phenomena
• Verf.angabe: Klaus Ambos-Spies and Thorsten Kräling
• E-Jahr: 2010
• Jahr: 27 October 2010
• Umfang: 16 S.
• Fussnoten: Gesehen am 22.11.2022
• Titel Quelle: Enthalten in: Mathematical structures in computer science
• Ort Quelle: Cambridge : Cambridge Univ. Press, 1991
• Jahr Quelle: 2010
• Band/Heft Quelle: 20(2010), 5, Seite 707-722
• ISSN Quelle: 1469-8072
• DOI: doi:10.1017/S0960129510000174
• Datenträger: Online-Ressource
• Sprache: eng
• K10plus-PPN: 1823172377

Abstract

We show that, for any abstract complexity measure in the sense of Blum and for any computable function f (or computable operator F), the class of problems that are f-speedable (or F-speedable) does not have effective measure 0. On the other hand, for sufficiently fast growing f (or F), 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.