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

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] L. Bass and P. Young, Hierarchies based on computational complexity and irregularities of class determining measured sets, J. Assoc. Comput. Mach. 20 (1973). MR 0339541 (49:4299)
  • [2] M. Blum, A machine-independent theory of the complexity of recursive functions, J. Assoc. Comput. Mach. 14 (1967), 322-336. MR 38 #4213. MR 0235912 (38:4213)
  • [3] -, On effective procedures for speeding up algorithms, J. Assoc. Comput. Mach. 18 (1971), 290-305. MR 0290884 (44:8063)
  • [4] A. Borodin, Computational complexity and the existence of complexity gaps, J. Assoc. Comput. Mach. 19 (1972), 158-174. MR 0321355 (47:9888)
  • [5] R. Constable, The operator gap. J. Assoc. Comput. Mach. 19 (1972), 175-183. MR 0314608 (47:3159)
  • [6] J. Hartmanis and J. Hopcroft, An overview of the theory of computational complexity, J. Assoc. Comput. Mach. 18 (1971), 444-475. MR 0288028 (44:5226)
  • [7] John Helm, On effectively computable operators, Z. Math Logik Grundlagen Math. 17 (1971), 231-244. MR 0286656 (44:3865)
  • [8] J. Helm and P. Young, On size vs. efficiency for programs admitting speed-ups, J. Symbolic Logic 36 (1971), 21-27. MR 0305991 (46:5119)
  • [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] A. Meyer and P. Fischer, Computational speed-up by effective operators, Project MAC Report, Summer 1970; J. Symbolic Logic 37 (1972), 48-68. MR 0317908 (47:6457)
  • [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, New York, 1967. MR 37 #61. MR 0224462 (37:61)
  • [13] P. Young, Speed-ups by changing the order in which sets are enumerated, Math. Systems Theory 5 (1971), 148-156; minor correction, ibid. 6 (1972). MR 0305653 (46:4783)

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

American Mathematical Society