Hostname: page-component-6898cfcb55-zkb6p Total loading time: 0 Render date: 2026-11-11T14:26:25.224Z Has data issue: false hasContentIssue false
  • English
  • Français

Quantitative aspects of speed-up and gap phenomena

Published online by Cambridge University Press:  27 October 2010

KLAUS AMBOS-SPIES and
THORSTEN KRÄLING
KLAUS AMBOS-SPIES
Affiliation:
Institut für Informatik, University of Heidelberg, INF 294, D-69120 Heidelberg, Germany Email: ambos@math.uni-heidelberg.de; thorsten.kraeling@informatik.uni-heidelberg.de
THORSTEN KRÄLING
Affiliation:
Institut für Informatik, University of Heidelberg, INF 294, D-69120 Heidelberg, Germany Email: ambos@math.uni-heidelberg.de; thorsten.kraeling@informatik.uni-heidelberg.de
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

References

Ambos-Spies, K. (1996) Resource-bounded genericity. In: Cooper, S., Slaman, T. and Wainer, S. (eds.) Computability, enumerability, unsolvability: Directions in recursion theory, Cambridge University Press 1–60.Google Scholar
Ambos-Spies, K. and Mayordomo, E. (1997) Resource-bounded measure and randomness. In: Sorbi, A. (ed.) Complexity, Logic and Recursion Theory, Dekker 1–47.Google Scholar
Ambos-Spies, K. and Reimann, J. (1997) Effective Baire category concepts. In: Proc. Sixth Asian Logic Conference 1996, Singapore University Press 13–29.Google Scholar
Blum, M. (1967) A machine-independent theory of the complexity of recursive functions. Journal of the ACM 14 (2)322–336.Google Scholar
Borodin, A. (1972) Computational complexity and the existence of complexity gaps. Journal of the ACM 19 (1)158–174.CrossRefGoogle Scholar
Calude, C. and Zimand, M. (1996) Effective category and measure in abstract complexity theory. Theoretical Computer Science 154 (2)307–327.CrossRefGoogle Scholar
Kräling, T. (2008) A Quantitative Analysis of the Speed-Up Theorem, Diplomarbeit, Universität Heidelberg, Fakultät für Mathematik und Informatik.Google Scholar
Lutz, J. (1992) Almost everywhere high nonuniform complexity. Journal of Computer and System Sciences 44 220–258.CrossRefGoogle Scholar
Mayordomo, E. (1994) Almost every set in exponential time is P-bi-immune. Theoretical Computer Science 136 487–506.CrossRefGoogle Scholar
Mehlhorn, K. (1973) On the size of sets of computable functions. In: Proceedings of the 14th IEEE Symposium on Switching and Automata Theory 190–196.Google Scholar
Meyer, A. R. and Fischer, P. C. (1972) Computational speed-up by effective operators. Journal of Symbolic Logic 37 (1)55–68.Google Scholar
Schnorr, C. (1973) Process complexity and effective random tests. Journal of Computer and System Sciences 7 376–388.Google Scholar
Trakhtenbrot, B. A. (1967) Complexity of algorithms and computations. Course Notes, Novosibirsk (in Russian).Google Scholar
Zimand, M. (2006) Computational Complexity: A Quantitative Perspective, Elsevier.Google Scholar