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

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

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