Hostname: page-component-745bb68f8f-s22k5 Total loading time: 0 Render date: 2025-01-24T06:51:31.685Z 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: [email protected]; [email protected]
THORSTEN KRÄLING
Affiliation:
Institut für Informatik, University of Heidelberg, INF 294, D-69120 Heidelberg, Germany Email: [email protected]; [email protected]
Get access Rights & Permissions [Opens in a new window]

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.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 20 , Special Issue 5: Theory and Applications of Models of Computation (TAMC 2008–2009) , October 2010 , pp. 707 - 722
Copyright
Copyright © Cambridge University Press 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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