Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Easy constructions in complexity theory: Gap and speed-up theorems

Author: Paul Young
Journal: Proc. Amer. Math. Soc. 37 (1973), 555-563
MSC: Primary 68A20; Secondary 02F15
MathSciNet review: 0312768
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Perhaps the two most basic phenomena discovered by the recent application of recursion theoretic methods to the developing theories of computational complexity have been Blum's speed-up phenomena, with its extension to operator speed-up by Meyer and Fischer, and the Borodin gap phenomena, with its extension to operator gaps by Constable. In this paper we present a proof of the operator gap theorem which is much simpler than Constable's proof. We also present an improved proof of the Blum speed-up theorem which has a straightforward generalization to obtain operator speed-ups. The proofs of this paper are new; the results are not. The proofs themselves are entirely elementary: we have eliminated all priority mechanisms and all but the most transparent appeals to the recursion theorem. Even these latter appeals can be eliminated in some ``reasonable'' complexity measures. Implicit in the proofs is what we believe to be a new method for viewing the construction of ``complexity sequences."

References [Enhancements On Off] (What's this?)

  • [1] Leonard Bass and Paul Young, Ordinal hierarchies and naming complexity classes, J. Assoc. Comput. Mach. 20 (1973), 668–686. MR 0339541
  • [2] Manuel Blum, A machine-independent theory of the complexity of recursive functions., J. Assoc. Comput. Mach. 14 (1967), 322–336. MR 0235912
  • [3] Manuel Blum, On effective procedures for speeding up algorithms, J. Assoc. Comput. Mach. 18 (1971), 290–305. MR 0290884
  • [4] A. Borodin, Computational complexity and the existence of complexity gaps, J. Assoc. Comput. Mach. 19 (1972), 158–174; corrigendum, ibid. 19 (1972), 576. MR 0321355
  • [5] Robert L. Constable, The operator gap, J. Assoc. Comput. Mach. 19 (1972), 175–183. MR 0314608
  • [6] J. Hartmanis and J. E. Hopcroft, An overview of the theory of computational complexity, J. Assoc. Comput. Mach. 18 (1971), 444–475. MR 0288028
  • [7] John P. Helm, On effectively computable operators, Z. Math. Logik Grundlagen Math. 17 (1971), 231–244. MR 0286656
  • [8] John Helm and Paul Young, On size vs. efficiency for programs admitting speed-ups, J. Symbolic Logic 36 (1971), 21–27. MR 0305991
  • [9] E. McCreight and A. Meyer, Classes of computable functions defined by bounds on computation, Proc. First Annual ACM Sympos. on Theory of Computing, pp. 79-88.
  • [10] Albert R. Meyer and Patrick C. Fischer, Computational speed-up by effective operators, J. Symbolic Logic 37 (1972), 55–68. MR 0317908
  • [11] A. Meyer and R. Moll, Honest bounds for complexity classes of recursive functions, Project MAC Report, April 1972.
  • [12] Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
  • [13] Paul Young, Speed-ups by changing the order in which sets are enumerated, Math. Systems Theory 5 (1971), 148–156. MR 0305653

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 68A20, 02F15

Retrieve articles in all journals with MSC: 68A20, 02F15

Additional Information

Keywords: Recursive function theory, computational complexity, speedup theorems, gap theorems, Blum theory
Article copyright: © Copyright 1973 American Mathematical Society