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

DOI:
https://doi.org/10.1090/S0002-9939-1973-0312768-7

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."

**[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)**

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

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

Additional Information

DOI:
https://doi.org/10.1090/S0002-9939-1973-0312768-7

Keywords:
Recursive function theory,
computational complexity,
speedup theorems,
gap theorems,
Blum theory

Article copyright:
© Copyright 1973
American Mathematical Society